Mathematical induction proving the final step

Question

Use mathematical induction to prove that $$ \frac12 + \frac16 + \ldots + \frac{1}{n(n+1)} = 1 - \frac{1}{n+1} $$

I am unsure about the prove n+1 step! I let $$ \frac12 + \frac16 + \ldots + \frac{1}{n(n+1)} = 1 - \frac{1}{n+1} $$ So I had $1 - \frac{1}{n+1} + (n+1)$ on the left hand side I unsure about the final steps.

Answer 1

HINT

General induction proofs look something like the following.

Base Case. Let $n=1$, can you validate it?

Inductive Step. Assume the statement holds for some fixed $n$, in other words, we assume $$ \frac12 + \frac16 + \ldots + \frac{1}{n(n+1)} = 1 - \frac{1}{n+1} $$ and we have to prove it for $n+1$, in other words, we must show that $$ \frac12 + \frac16 + \ldots + \frac{1}{n(n+1)} + \frac{1}{(n+1)(n+2)} = 1 - \frac{1}{n+2}. $$ But from the inductive assumption, LHS simplifies to $$ 1 - \frac{1}{n+1} + \frac{1}{(n+1)(n+2)} = 1 - \frac{1}{n+1} + \left[\frac{1}{n+1} - \frac{1}{n+2}\right] = 1 - \frac{1}{n+2}. $$ Can you complete the proof?

Answer 2

base case n = 1

$\frac 12 = 1 - \frac 12$

Hypothesis:

Suppose $\frac 12 + \frac 16 + \cdots + \frac {1}{n(n+1)} = 1 - \frac {1}{n+1}$

$\frac 12 + \frac 16 + \cdots + \frac {1}{n(n+1)} + \frac {1}{(n+1)(n+2)} = 1 - \frac 1{n+1} + \frac {1}{(n+1)(n+2)}$ By the inductive hypothesis.

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

QED

Answer 3

Compare both expressions (I've named your sum $S_n$) and see what is different

$$S_n=\frac12 + \frac16 + \ldots + \frac{1}{n(n+1)}\tag{1}$$

$$S_{n+1}=\frac12 + \frac16 + \ldots + \frac{1}{n(n+1)} +\frac{1}{(n+1)(n+2)}\tag{2}$$

How can you get from $(1)$ to $(2)$? Once you know that you have your induction step.

Answer 4

Overview of Induction:

Keep in mind that an induction proof consists of three parts:

• Proving a base case.
• Assuming that the hypothesis you're proving holds for some $n$, where $n$ is greater than whatever value your base case used for $n$. So if you used $n=1$ in the base case, you might say "assume that, for $n = k$, (the thing you're trying to prove) holds".
• Proving that, under this hypothesis in the previous step, that the successive step is implied. That is, "our base case and our induction hypothesis imply the formula holds for $n = k+1$. The bolded is very, very important: it generally falls apart if you don't use the induction hypothesis (the second step that you assume holds).

---

Applying This To Your Case:

So in your case, we have

• Base case: Assume $n=1$ and verify the formula that results. Pretty trivial, basically amounts to $1/2 = 1/2$.
• Induction hypothesis: Assume that the formula holds for $n=k$, i.e. we assume

$$\frac{1}{2} + \frac{1}{6} + \frac{1}{12} + ... + \frac{1}{k(k+1)} = \sum_{n=1}^{k} \frac{1}{n(n+1)} = 1 - \frac{1}{k+1}$$

• Induction: Verification for $n=k+1$, i.e. showing from the previous

$$\frac{1}{2} + \frac{1}{6} + \frac{1}{12} + ... + \frac{1}{k(k+1)} + \frac{1}{k+1(k+2)} = \sum_{n=1}^{k+1} \frac{1}{n(n+1)} = 1 - \frac{1}{(k+1)+1} = 1 - \frac{1}{k+2}$$

---

How We Verify The Induction:

We notice: we can pull out the last term (where $n=k+1$) of the summation:

$$\sum_{n=1}^{k+1} \frac{1}{n(n+1)} = \frac{1}{(k+1)(k+2)} + \sum_{n=1}^{k} \frac{1}{n(n+1)}$$

This second sum? It's implied by our induction hypothesis to be $1 - \frac{1}{k+1}$ and thus

$$\sum_{n=1}^{k+1} \frac{1}{n(n+1)} = \frac{1}{(k+1)(k+2)} + 1 - \frac{1}{k+1}$$

Simplify the latter sum and we get

$$\sum_{n=1}^{k+1} \frac{1}{n(n+1)} = \frac{1+(k+1)(k+2)-(k+2)}{(k+1)(k+2)} = \frac{1+k^2 +3k +2-k-2}{(k+1)(k+2)} = \frac{k^2+2k+1}{(k+1)(k+2)} = \frac{(k+1)(k+1)}{(k+1)(k+2)} = \frac{k+1}{k+2}$$

We make use of a handy trick here:

$$k+1 = (k+1)+(1-1) = (k+1+1)-1=(k+2)-1$$

Then...

$$\sum_{n=1}^{k+1} \frac{1}{n(n+1)} = \frac{k+1}{k+2} = \frac{(k+2)-1}{k+2} = \frac{k+2}{k+2} - \frac{1}{k+2} = 1 - \frac{1}{k+2}$$

Notice: this is what we sought to verify in our induction step. Thus, the induction is completed.