# 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 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 at 17:40

## 2 Answers

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.)

• Thank you for a nice generating function for Question 1. – T. Amdeberhan May 5 at 16:30

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.

• Thank you for a nice recursive approach to Question 1. – T. Amdeberhan May 5 at 16:31