Summation of series in powers of x with certain combinations as coefficients How can I find the sum: $$\sum_{k=0}^{n} \binom{n-k}{k}x^{k}$$
Edit: The answer to this question is: $$\frac{{(1+\sqrt{1+4x})}^{n+1}-{(1-\sqrt{1+4x})}^{n+1}}{2^{n+1}\sqrt{1+4x}}$$ I don't know how to arrive at this answer.
 A: This answer is similar to this answer and this answer. That is, compute the generating function of the given sequence:
$$
\begin{align}
&\sum_{n=0}^\infty\sum_{k=0}^n\binom{n-k}{k}x^ky^n\\
&=\sum_{k=0}^\infty\sum_{n=k}^\infty\binom{n-k}{k}x^ky^n\tag{1}\\
&=\sum_{k=0}^\infty\sum_{n=0}^\infty\binom{n}{k}x^ky^{n+k}\tag{2}\\
&=\sum_{k=0}^\infty\frac{(xy^2)^k}{(1-y)^{k+1}}\tag{3}\\
&=\frac1{1-y}\frac1{1-\frac{xy^2}{1-y}}\tag{4}\\
&=\frac1{1-y-xy^2}\tag{5}\\
&=\frac1{\left(1-\frac{1-\sqrt{1+4x}}2y\right)\left(1-\frac{1+\sqrt{1+4x}}2y\right)}\tag{6}\\
&=\frac{\frac{-1+\sqrt{1+4x}}{2\sqrt{1+4x}}}{1-\frac{1-\sqrt{1+4x}}2y}+\frac{\frac{1+\sqrt{1+4x}}{2\sqrt{1+4x}}}{1-\frac{1+\sqrt{1+4x}}2y}\tag{7}\\
&=\frac1{\sqrt{1+4x}}\sum_{n=0}^\infty\left[\left(\frac{1+\sqrt{1+4x}}2\right)^{n+1}-\left(\frac{1-\sqrt{1+4x}}2\right)^{n+1}\right]y^n\tag{8}
\end{align}
$$
Explanation:
$(1)$: change order of summation
$(2)$: substitute $n\mapsto n+k$
$(3)$: $\sum\limits_{n\ge k}\binom{n}{k}y^n=\frac{y^k}{(1-y)^{k+1}}$
$(4)$: $\sum\limits_{k\ge 0}x^k=\frac1{1-x}$
$(5)$: simplify
$(6)$: quadratic formula
$(7)$: partial fractions
$(8)$: $\sum\limits_{n\ge 0}x^n=\frac1{1-x}$
Equating coefficients of $y^n$ yields
$$
\sum_{k=0}^n\binom{n-k}{k}x^k
=\frac1{\sqrt{1+4x}}\left[\left(\frac{1+\sqrt{1+4x}}2\right)^{n+1}-\left(\frac{1-\sqrt{1+4x}}2\right)^{n+1}\right]
$$
A: Introduce the generating function
$$f(z) = \sum_{n\ge 0} z^n \sum_{k=0}^n {n-k\choose k} x^k.$$
This becomes
$$f(z) = \sum_{k\ge 0} x^k 
\sum_{n\ge k} z^n {n-k\choose k}
\\ = \sum_{k\ge 0} x^k 
\sum_{n\ge 0} z^{n+k} {n\choose k}
= \sum_{k\ge 0} x^k 
\sum_{n\ge k} z^{n+k} {n\choose k}
\\ = \sum_{k\ge 0} x^k 
\sum_{n\ge 0} z^{n+2k} {n+k\choose k}
= \sum_{k\ge 0} x^k z^{2k}
\sum_{n\ge 0} z^{n} {n+k\choose k}
\\ = \sum_{k\ge 0} x^k z^{2k}
\frac{1}{(1-z)^{k+1}}
= \frac{1}{1-z} \frac{1}{1-xz^2/(1-z)}
\\ = \frac{1}{1-z-xz^2}
= -\frac{1/x}{z^2+z/x-1/x}.$$
Solving $z^2+z/x-1/x$ we obtain $$\rho_{1,2}
= \frac{-1 \pm\sqrt{1+4x}}{2x}$$
and we have that
$$f(z) = -\frac{1}{x}\frac{1}{(z-\rho_1)(z-\rho_2)}
\\ = -\frac{1}{x}
\frac{1}{\rho_1-\rho_2}
\left(\frac{1}{z-\rho_1}-\frac{1}{z-\rho_2}\right)
\\ = -\frac{1}{x}
\frac{1}{\rho_1-\rho_2}
\left(\frac{1}{\rho_1}\frac{1}{z/\rho_1-1}
-\frac{1}{\rho_2}\frac{1}{z/\rho_2-1}\right).$$
Extracting coefficients from this we obtain
$$-\frac{1}{x}
\frac{x}{\sqrt{1+4x}}
\left(-\frac{1}{\rho_1^{n+1}}
+\frac{1}{\rho_2^{n+1}}\right).$$
Now since $\rho_1\rho_2 = -1/x$ this becomes
$$-\frac{1}{\sqrt{1+4x}}
\left(-(-1)^{n+1} x^{n+1} \rho_2^{n+1}
+(-1)^{n+1} x^{n+1} \rho_1^{n+1}\right).$$
Observe that
$$(-1)^{n+1} x^{n+1} \rho_{1,2}^{n+1}
= \frac{(1\mp\sqrt{1+4x})^{n+1}}{2^{n+1}}$$
so this finally becomes
$$-\frac{1}{\sqrt{1+4x}}
\frac{(1-\sqrt{1+4x})^{n+1}-(1+\sqrt{1+4x})^{n+1}}
{2^{n+1}}
\\ = \frac{1}{\sqrt{1+4x}}
\frac{(1+\sqrt{1+4x})^{n+1}-(1-\sqrt{1+4x})^{n+1}}
{2^{n+1}}.$$

Alternate derivation of the generating function.
Introduce
$${n-k\choose k}
= \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n-k}}{z^{k+1}} dz.$$
This yields for the sum
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n}}{z} 
\sum_{k=0}^n \frac{x^k}{(1+z)^k z^k} \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{(1+z)^{n}}{z}
\frac{x^{n+1}/(1+z)^{n+1}/z^{n+1}-1}
{x/(1+z)/z-1} \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} (1+z)^{n+1}
\frac{x^{n+1}/(1+z)^{n+1}/z^{n+1}-1}
{x-z-z^2} \; dz.$$
We omit the part that does not contribute to get
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} (1+z)^{n+1}
\frac{x^{n+1}/(1+z)^{n+1}/z^{n+1}}
{x-z-z^2} \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}}
\frac{x^{n+1}}{x-z-z^2} \; dz.$$
This is
$$[z^n] \frac{x^{n+1}}{x-z-z^2}
= x [z^n] x^{n} \frac{1}{x-z-z^2} 
\\ = x [z^n] \frac{1}{x-zx-z^2x^2} 
= [z^n] \frac{1}{1-z-z^2x}.$$
We have the same generating function as above, QED.
A: $$\begin{align}F(n) = \sum_{k=0}^{n} \binom{n-k}{k} x^k &= \sum_{k=0}^{n} \left(\binom{n-k-1}{k} + \binom{n-k-1}{k-1}\right) x^k
\\&=\sum_{k=0}^{n} \binom{n-k-1}{k} x^k +\sum_{k=0}^{n} \binom{n-k-1}{k-1} x^k\end{align}$$
$$\sum_{k=0}^{n} \binom{n-k-1}{k} x^k=\sum_{k=0}^{n-1} \binom{(n-1)-k}{k} x^k
=F(n-1)$$ because when $k=n$, $\displaystyle \binom{(n-1)-k}{k}$ is $0$.
Similarly , $\displaystyle \sum_{k=0}^{n} \binom{n-k-1}{k-1} x^k=\sum_{k=-1}^{n-1} \binom{n-2-k}{k} x^{k+1} =xF(n-2)$ shifiting $k$ by $1$.
So , $F(n)=F(n-1)+xF(n-2)$
also you can get the closed form similar to fibonacci analysis.
