Proof by induction with factorials

Question

I need help with proving this:

$$\sum_{i=1}^n \frac{i-1}{i!}=\frac{n!-1}{n!}$$

My induction hypothesis is:

$$\sum_{i=1}^{n+1} = \sum_{i=1}^n \frac{i-1}{i!}+\frac{(n+1)!-1}{(n+1)!}=\frac{(n+1)!-1}{(n+1)}$$

I tried a few things and landed here:

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

there is one $n$ too much in my last equation and I don't know how to get rid of it.

Thanks for your help.

Answer 1

HINT: you must prove that $$\frac{n!-1}{n!}+\frac{n+1-1}{(n+1)!}=\frac{(n+1)!-1}{(n+1)!}$$

Answer 2

You want to change the indices on the first sum of $$\sum_{i=1}^{n+1} \frac{n!-1}{n!}+\frac{(n+1)!-1}{(n+1)!}=\frac{(n+1)!-1}{(n+1)}$$ to $$\sum_{i=1}^{n+1} \frac{i!-1}{i!}+\frac{(n+1)!-1}{(n+1)!}=\frac{(n+1)!-1}{(n+1)}$$

Answer 3

Your induction hypothesis should be the formula you're trying to prove. As in:

Assume $\sum_{i=1}^n \frac{i-1}{i!}=\frac{n!-1}{n!}$

You're trying to prove the formula obtained by replacing every copy of $n$ with $n+1$ in the above formula. As in:

We wish to show that $\sum_{i=1}^{n+1} \frac{i-1}{i!}=\frac{(n+1)!-1}{(n+1)!}$

Does that help?

Answer 4

You know that $$\sum_{i=1}^n \frac{i-1}{i!}=\frac{n!-1}{n!}\ \ \ \ \ (1)$$ You want to prove if $$\sum_{i=1}^{n+1} \frac{i-1}{i!}=\frac{(n+1)!-1}{(n+1)!}$$ Then $$\sum_{i=1}^{n} \frac{i-1}{i!}+\frac{(n+1)-1}{(n+1)!}=\frac{(n+1)!-1}{(n+1)!}\underbrace{\implies}_{(1)}\frac{n!-1}{n!}+\frac{(n+1)-1}{(n+1)!}=\frac{(n+1)!-1}{(n+1)!}$$

Answer 5

"My induction hypothethesis is

$\sum_{i=1}^{n+1} = \sum_{i=1}^n \frac{i-1}{i!}+\frac{(n+1)!-1}{(n+1)!}=\frac{(n+1)!-1}{(n+1)}$"

WHY?!?!?!?!?!?!?!?

$\sum_{i=1}^{n+1}\frac {i -1}{i} = \sum_{i=1}^n \frac {i-1}{i} + \frac {n+ 1 - 1}{(n+1)!}$ and $\frac {n+1 - 1}{(n+1)!} \ne \frac{(n+1)!-1}{(n+1)!}$ And setting $n\to n+1$ will give you $\frac {n!-1}{n!} \to \frac {(n+1)! - 1}{(n+1)!}$ and not $\frac{(n+1)! - 1}{n+1}$.

Surely you induction hypothethesis should have been

$\sum_{i=1}^{n+1}\frac {i -1}{i} = \sum_{i=1}^n \frac {i-1}{i} + \frac {n+ 1 - 1}{(n+1)!}= \frac {(n+1)! -1}{(n+1)!}$

Which is a matter of proving

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

which should be very easy to prove:

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

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

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

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