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$
5
  • $\begingroup$ Hint: $(1-x)^{-(n+1)}=\frac{(1-x)^{n}}{(1-x)}$ $\endgroup$
    – AvZ
    Jan 21, 2015 at 10:06
  • $\begingroup$ Does it really..? $\endgroup$
    – Gudushen
    Jan 21, 2015 at 10:32
  • $\begingroup$ I said this because if you use this result initially, you can prove this by induction. $\endgroup$
    – AvZ
    Jan 21, 2015 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, 2015 at 10:35
  • $\begingroup$ My bad. You're cprrect $\endgroup$
    – AvZ
    Jan 21, 2015 at 10:36

1 Answer 1

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.