1. ## Prove by Induction

$\displaystyle \sum_{n=0}^\infty {{n+k} \choose k}\ x^n = {1 \over {(1-x})^{k+1}}$

where $\displaystyle |x| < 1$

Can anyone lead me here? Such questions get the better of me all the time. How should I go about improving?
Much appreciated.

2. Let K = 0.
LHS = $\displaystyle 1 + x + x^2 + x^3 + ....= {1 \over {1 - x}}$= RHS

using the summation of geometric progression $\displaystyle {a \over {1 - r}}$

For K = 2,
LHS = $\displaystyle {2 \choose 2} x^0 + {3 \choose 2} x^1 + {4 \choose 2} x^2 + ... \ \ \ = \ 1 + 3x + 6x^2 + 10x^3 + ...$

Now I cannot use the geometric progression, and hence I come unstuck.

For RHS,
its $\displaystyle {1 \over {1 - 3x + 3x^2 - x^3}} = {1 \over {{\sum_{k=0}^3} {3 \choose k} (-x)^k}}$

using Binomial Theorem

3. Originally Posted by chopet
$\displaystyle \sum_{n=0}^\infty {{n+k} \choose k}\ x^n = {1 \over {(1-x})^{k+1}}$

where $\displaystyle |x| < 1$

Can anyone lead me here? Such questions get the better of me all the time. How should I go about improving?
Much appreciated.
I don't have the time right now, but to me it looks like a job for an induction proof.

-Dan

4. Use generating functions,
$\displaystyle \frac{1}{1-x} = 1+x+x^2+x^3+...$
So,
$\displaystyle \frac{1}{(1-x)^{k+1}} = \frac{1}{1-x}\cdot ... \cdot \frac{1}{1-x}$.
Which becomes,
$\displaystyle (1+x+x^2+...)(1+x+x^2+...)...(1+x+x^2+...)$
Which is the LHS.