Ask Me Help Desk - How to solve by using induction?

Quote:

Originally Posted by tikki14

How to solve this equation by using induction?

$\frac{(n+1)!}{1!} + \frac{(n+2)!}{2!} + ... + \frac{(n+p)!}{(p!)} = \frac{1}{n+1} \[ \frac{(n+p+1)!}{p!} - (n+1)!\]$

for n=k:

$\frac{(k+1)!}{1!} + \frac{(k+2)!}{2!} + ... + \frac{(k+p)!}{p!} = \frac{1}{k+1} \[ \frac{(k+p+1)!}{p!} - (k+1)! \]$

for n=k+1:

$\frac{(k+2)!}{1!} + \frac{(k+3)!}{2!} + ... + \frac{(k+p+1)!}{p!} = \frac{1}{k+2} \[ \frac{(k+p+2)!}{p!} - (k+2)! \]$

$\frac{(k+2)!}{1!} + \frac{(k+3)!}{2!} + ... + \frac{(k+p+1)!}{p!} = \frac{(k+1)!}{1!} + 2 \times \frac{(k+2)!}{2!} + ... + p \times \frac{(k+p)!}{p!} + \frac{(k+p+1)!}{p} - (k+1)!$

Is it correct by now? If yes, what should I do next?

This proof is MUCH easier if you increment p instead of n.

For proof by induction, we take the given equation as true. Then we replace p with p+1:

$\frac{(n+1)!}{1!}+\frac{(n+2)!}{2!}+...+\frac{(n+p )!}{p!}+\frac{(n+p+1)!}{(p+1)!}=\frac{1}{n+1}\[ \frac{(n+p+2)!}{(p+1)!}- (n+1)! \]$

But the first p terms of the left side are the left side of the given equation (which we assume is true for proof by induction), so we can replace those terms with the right side of the given equation and write:

$\frac{1}{n+1}\[ \frac{(n+p+1)!}{p!}- (n+1)! \] +\frac{(n+p+1)!}{(p+1)!}=\frac{1}{n+1}\[ \frac{(n+p+2)!}{(p+1)!}- (n+1)! \]$

Now if we can show that the two sides are indeed equal, we will have succeeded in proof by induction.

First, let's get rid of the 1/(n+1):

$\frac{(n+p+1)!}{p!}- (n+1)! +\frac{(n+1)(n+p+1)!}{(p+1)!}=\frac{(n+p+2)!}{(p+1 )!}- (n+1)!$

Now we can lose the -(n+1)! Terms on both sides and get a common denominator of (p+1)!:

$\frac{(p+1)(n+p+1)!}{(p+1)!} +\frac{(n+1)(n+p+1)!}{(p+1)!}=\frac{(n+p+2)!}{(p+1 )!}$

Now we get rid of the denominator and factor out a (n+p+1)! Term on the left side:

$$(p+1)+(n+1)$(n+p+1)!=(n+p+2)!$

$$n+p+2$(n+p+1)!=(n+p+2)!$

$(n+p+2)!=(n+p+2)!$

Q.E.D.