Derivatives of the geometric series to prove equality

114 Views Asked by At

I have to show that

$(1-p)^{-r} = \sum_{k=0}^{\infty} \binom{k+r-1}{k}p^k$ where $p \in (0,1)$ and $r \in \mathbb{N}_{\geq 1}$.

I got the hint that I have to consider the derivatives of the geometric series. Those would be:

$\sum_{k=1}^{\infty} kx^{k-1}, \sum_{k=2}^{\infty}\frac{(n-1)n}{2}x^{n-2}, \dots$

I don't see the pattern to somehow connect this to prove my equality.

SOLUTION

We will prove the statement by induction.

Base case: $r=1$

$(1-p)^{-1} = \sum_{k=0}^{\infty} p ^k$ (geometric series), hence base case is true

Induction step: Assume $(1-p)^{-r} = \sum_{k=0}^{\infty} \binom{k+r-1}{k}p^k$ for some $r$. We will show that it is true for $r+1$.

$(1-p)^{-(r+1)}= \sum_{k=0}^{\infty} \binom{k+r-1}{k}p^k \sum_{k=0}^{\infty}p^k$

Using the Cauchy-Product we get:

$=\sum_{k=0}^{\infty} p^k\sum_{n=0}^k \binom{n+r-1}{n} $

Sub-Claim $\sum_{n=0}^k \binom{n+r-1}{n} = \binom{k+r}{k}$

Base-Case: $k=0$ is true

Induction-step: Assume $\sum_{n=0}^k \binom{n+r-1}{n} = \binom{k+r}{k}$ for some $k$. We will show it for $k+1$.

$\sum_{n=0}^{k+1}\binom{n+r-1}{n} = \binom{k+1+r-1}{k+1} + \binom{k+r}{k} = \binom{k+1+r}{k+1}$

$\implies $ Sub-claim is true.

We will continue with our first induction:

$=\sum_{k=0}^{\infty} p^k\sum_{n=0}^k \binom{n+r-1}{n} $

$=\sum_{k=0}^{\infty} p^k \binom{k+r}{k}$

$\implies$ Claim proven

1

There are 1 best solutions below

2
On BEST ANSWER

The solution using derivatives can also be done via induction. In this approach the key is to know that a power series can be differentiated term by term in the interior of region of convergence.

Like your solution we see that the base case for $r=1$ is true. Assume it to be true for $r$ so that $$(1-p)^{-r}=\sum_{k=0}^{\infty} \binom{k+r-1}{k}p^k\tag{1}$$ Differentiating it with respect to $p$ we get $$(-r) (1-p)^{-r-1}(-1)=\sum_{k=1}^{\infty} k\binom{k+r-1}{k}p^{k-1}$$ Note that the first term for $k=0$ in right side of equation $(1)$ is a constant $1$ so on differentiation this becomes $0$ and I have removed it altogether so that the summation index now starts from $k=1$. Next I shift the summation index $k$ by $1$ so that it again starts from $0$ and thus the above equation is written as $$r(1-p)^{-(r+1)}=\sum_{k=0}^{\infty} (k+1)\binom{k+r}{k+1}p^k$$ or $$(1-p)^{-(r+1)}=\sum_{k=0}^\infty \frac{k+1}{r}\binom{k+r}{k+1}p^k\tag{2}$$ Next observe that $$\frac{k+1}{r}\binom{k+r}{k+1}=\frac{k+1}{r} \frac{(k+r)!}{(k+1)!(r-1)!}=\frac{(k+r)!}{k!r!}=\binom{k+r}{k}$$ And therefore equation $(2)$ can be rewritten as $$(1-p)^{-(r+1)}=\sum_{k=0}^{\infty} \binom{k+r} {k} p^k\tag{3}$$ which shows that the formula holds for $r+1$ also. The proof is now complete by induction.

You should observe that this approach requires similar amount of work as compared to the solution given in question.