1. ## Mathematical induction

Can anyone explain mathematical induction to me? I have a whole chapter worth of problems and do not even begin to understand.

Here are a couple of examples:
Show that 1^3+2^3+...+n^3=[n(n+1)/2]^2 whenever n is a positive integer.

Use mathematical induction to prove that n!<n^n whenever n is a postive integer greater than 1.

2. Hello,

Sorry for the "innovation", but I copied it from one of my other posts..

Ok, there are three main steps in an induction proof

Preliminary : state the induction property $P_n$

This is mostly for yourself, to clear out the view.

1st step : the basis.
You have to check that this is true for the very first term.

2nd step : the inductive step.
Induction hypothesis : assume that the property is true for a rank n.

Then, prove that if this is verified for a rank n, it will be for the following rank, n+1.

In most of the induction exercises, this proof will require you to go back to the recursive definition of $P_n$
Also see here : Mathematical induction - Wikipedia, the free encyclopedia

-----------------------------
Here, $P_n \ : \ 1^3+2^3+...+n^3=\left[\frac{n(n+1)}{2}\right]^2 ~,~$ $\text{whenever n is a positive integer, that is to say } n \ge 1$.

Basis : Prove that $P_1$ is true << this is easy here;

Inductive hypothesis : $1^3+2^3+...+n^3=\left[\frac{n(n+1)}{2}\right]^2$

Prove that $P_{n+1}$ is true : $1^3+2^3+...+n^3+(n+1)^3=\left[\frac{(n{\color{red}+1})(n+{\color{red}2})}{2}\rig ht]^2$.

proof :
$1^3+2^3+...+n^3+(n+1)^3=\left[\frac{n(n+1)}{2}\right]^2+(n+1)^3$, according to the inductive hypothesis.

$=\frac{[n(n+1)]^2}{4}+(n+1)^3$

$=\frac{n^2(n+1)^2+4(n+1)^3}{4}$

Factor by $(n+1)^2$:

$=\frac{(n+1)^2[{\color{blue}n^2+4(n+1)}]}{4}$ (1)

-----------------------------
On your draft paper, note that you have to prove that this is equal to $\frac{[(n+1)(n+2)]^2}{4}=\frac{(n+1)^2{\color{blue}(n+2)^2}}{4}$, that is to say prove that $n^2+4(n+1)=(n+2)^2$

-----------------------------

So factor (1) correctly, in order to get what you want...
In fact, you should always be able to keep in mind what formula you want to prove (the P_{n+1} thing).

Is it clear enough ?

3. Use mathematical induction to prove that n!<n^n whenever n is a postive integer greater than 1.
$P_n \ : \ n! < n^n ~,~ n \ge 2$.

$P_2 \ : \ 2!<2^2$ ???

2!=2
2²=4.

So $P_2$ is true.

----------------
Assume that $n! (inductive hypothesis).

Prove that $(n+1)!<(n+1)^{n+1}$.

$(n+1)^{n+1}=(n+1)^n \cdot (n+1)$

But $n+1>n \quad \implies \quad (n+1)^n>n^n$.

So we have $(n+1)^{n+1}>n^n \cdot (n+1)$.

The inductive hypothesis lets us know that $n^n>n!$.

Therefore $(n+1)^{n+1}>n^n \cdot (n+1)>n! \cdot (n+1)=(n+1)! \quad \square$

Do you understand it ?

4. I wish I did understand. I will look at your answers and really try to grasp this concept. I have only 18 problems left and I will be finished with this course (and thank goodness because I haven't understood a bit of it). Thank you for your help and I will look at it carefully to see if I can understand what you have written.