0
$\begingroup$

$$(1-x)^{-n} = \sum_{k\ge0}{k+n-1 \choose n-1}x^k$$

I'm supposed to prove this for any integer n $\ge$ 1 via induction on n. Base case where n = 1 is easy enough to prove, but what about the inductive case?

$\endgroup$
  • $\begingroup$ Hint: $(1-x)^{-(n+1)}=\frac{(1-x)^{n}}{(1-x)}$ $\endgroup$ – AvZ Jan 21 '15 at 10:06
  • $\begingroup$ Does it really..? $\endgroup$ – Gudushen Jan 21 '15 at 10:32
  • $\begingroup$ I said this because if you use this result initially, you can prove this by induction. $\endgroup$ – AvZ Jan 21 '15 at 10:34
  • $\begingroup$ What i meant is that doesnt (1-x)^n / (1-x) = (1-x)^n-1 instead of (1-x)^-n-1? or you meant that this is just a step in the induction process $\endgroup$ – Gudushen Jan 21 '15 at 10:35
  • $\begingroup$ My bad. You're cprrect $\endgroup$ – AvZ Jan 21 '15 at 10:36
0
$\begingroup$

Suppose the formula for $n$ is known. Writing $(1-x)^{-(n+1)}=\sum_kc_kx^k$ (with certainly $c_0=1$) one must have $(1-x)^{-n}=(1-x)\sum_kc_kx^k=1+\sum_{k>0}(c_k-c_{k-1})x^k$. That gives us the recurrence relation $c_k-c_{k-1}=\binom{k+n-1}{n-1}$ with $c_0=1$. It follows from Pascal's recurrence that $c_k=\binom{k+n}n$ satisfies this recurrence relation.


Alternatively to the final observation, you can use the well known fact that $\sum_{i=0}^k\binom{n-1+i}{n-1}=\binom{k+n}n$ to solve the recurrence (it really amounts to the same thing, Pascal's recurrence).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.