Mathematical Induction

**WartonMorton** · April 7th 2010, 08:01 AM

Please see attachment.
I know that math induction is when you prove the first term and then you have to prove for all the other terms with some sort of k+1? It's in a little bit different format than I'm used to so maybe that's why I am getting confused.

**emakarov** · April 7th 2010, 08:18 AM

The first step in an inductive proof is to form an inductive statement. It is an expression that depends on a variable $n$ . For each particular $n$ it is either true or false, but until $n$ is fixed, it does not have a truth value.

Statements proved by induction usually have the form "For all $n$ , $P(n)$ " for some expression $P$ . This $P$ that mentions $n$ is the inductive statement. Writing it explicitly: " $P(n)$ is ..." is an indispensable first step.

**WartonMorton** · April 7th 2010, 08:55 AM

where do the k's and k+1's come into play?

**Grandad** · April 7th 2010, 12:22 PM

Hello WartonMorton

Originally Posted by WartonMorton

Please see attachment.
I know that math induction is when you prove the first term and then you have to prove for all the other terms with some sort of k+1? It's in a little bit different format than I'm used to so maybe that's why I am getting confused.

The problem is this:

Use mathematical induction to prove the following assertion:

If $a_1 = 1$ and $a_{n+1}=a_n - \frac{1}{n(n+1)}$ , then $a_n = \frac1n$ .

The thing you have to prove here is that $a_n = \frac1n$ . This forms our 'inductive assertion' or 'induction hypothesis', that we can denote by $P(n)$ .

So $P(n)$ is the statement: $a_n = \frac1n$ .

We have no means of telling whether $P(n)$ is true yet. It is just a hypothesis. What we can do, though, is to make use of the definition of $a_{n+1}$ to deduce another statement that will follow if $P(n)$ is true. From this we hope to prove that $P(n) \Rightarrow P(n+1)$ (where $\Rightarrow$ means 'implies'), which is the basis of a proof by induction.

So we use the 'implies' sign, when we make this deduction. Like this:

$P(n) \Rightarrow a_n = \frac1n$

$\Rightarrow a_{n+1} = \frac1n-\frac{1}{n(n+1)}$ , using the definition of $a_n+1$ that we've been given.

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

$=\frac{1}{n+1}$

$\Rightarrow P(n+1)$

Do you understand that last step? We have shown that if $P(n)$ is true, then $a_{n+1} = \frac{1}{n+1}$ , which is simply $P(n+1)$ .

Finally we check that $P(1)$ is true. Which it is:

$a_1 = 1 = \frac{1}{1}$

This completes the proof.

Grandad

Thread: Mathematical Induction

LinkBack

Thread Tools

Display