# One generating function, two-fold sums

This comes out of a series of transformations, so I'll just get to the main focus here.

Define the functions $$F_n(x)=\frac12\left(x+2+2\sqrt{x+1}\right)^n+\frac12\left(x+2-2\sqrt{x+1}\right)^n. \tag1$$ It's straightforward to obtain $$F_n(x)=\sum_{r=0}^n\binom{2n}{2r}(x+1)^r. \tag2$$

QUESTION 1. On the other hand, how does one obtain (3) by manipulating (1)? $$F_n(x)=\sum_{r=0}^n\frac{n}{n+r}\binom{n+r}{2r}4^rx^{n-r}. \tag3$$

QUESTION 2. As an aside, I'd also be pleased with a combinatorial proof of the sums (2)=(3).

POSTSCRIPT. Question 1 has received ample response and thanks for those who did. I hope someone can address Question 2.

• This doesn't answer your questions, but (2) = (3) is a special case of Pfaff's transformation for the hypergeometric series. More precisely, Pfaff's transformation takes the reversel of (2) to (3). – Ira Gessel May 4 '19 at 0:07
• Another useful thing to know is that $x+2+2\sqrt{x+1} = (1+\sqrt{x+1})^2$. – Ira Gessel May 19 '19 at 17:40

Here's a sketch of a derivation of (3) from (1). It's fairly straightforward to compute $$\sum_{n=0}^\infty F_n(x) z^n = \frac{1-2z-xz}{(1-xz)^2 -4z}.$$ If you expand this in powers of $$z$$ you get (3). (You have to be careful with the constant term, where (3) is undefined.)
The Lucas polynomials $$L_n(x,s)=\sum_{j=0}^{\left\lfloor \frac{n}{2} \right\rfloor} \frac{n}{n-j}\binom{n-j}{j}s^jx^{n-2j}$$ satisfy the recursion $$L_n(x,s)=xL_{n-1}(x,s)+sL_{n-2}(x,s)$$ with initial values $$L_0(x,s)=2$$ and $$L_1(x,s)=x.$$
Binet’s formula gives $$L_n(x,s)= {\left( {\frac{{x + \sqrt {{x^2} + 4s} }}{2}} \right)^n} + {\left( {\frac{{x - \sqrt {{x^2} + 4s} }}{2}} \right)^n}.$$
For $$2F_n(x)=L_{2n}(2,x)$$ this reduces to your formulas.