Understanding Mathematical Induction problems

Question

I have problem to understand this 3 formulas, I am new in this type of problems. I have to solve this problems by induction.

\begin{align} \sum_{j = 1}^{j = n} j^3 &= \left(\frac{n(n + 1)}{2}\right) ^ 2 &\text{where } n \geq 1 \\ \sum_{j = 1}^{j = n} j(j + 1) &= \frac{1}{3}n(n + 1)(n + 2) & \text{where } n \geq 1 \\ \sum_{j = 1}^{j = n} j(j!) &= (n + 1)! - 1 \end{align}

Answer 1

The general procedure for a proof by induction is to first show that the base case satisfies that proposition. Then you assume that your proposition holds for some $n$ and show that from their you can get $n+1$ to work.

I'll work the first the one and let you try the others using the same procedure.

We need to show that when $n=1$ the statement is true. clearly $1^3 = (\frac{1*2}{2})^2$. Now we assume that the statement is true for some $n$. Then we compute:

$$\sum_{j=1}^{n+1}j^3 = \sum_{j=1}^{n}j^3 + (n+1)^3 = \left(\frac{n(n+1)}{2}\right)^2 + (n+1)^3 $$ $$ = \frac{n^2(n^2+2n+1)}{4} + (n^3+3n^2+3n+1)$$ $$ = \frac{n^4+2n^3+n^2}{4} + \frac{4(n^3+3n^2+3n+1)}{4}$$ $$ = \frac{n^4+6n^3+13n^2 + 12n+4}{4} = \left(\frac{(n+1)(n+2)}{2}\right)^2$$

Therefore the proposition holds for $n+1$ as well and so must hold for all $n$.

Conceptually think about it as a bunch of dominoes falling over one at a time. The base case guarantees that the first domino falls over, and the step of showing that you can get $n+1$ from the statement being true for $n$ is saying that any domino that falls will hit the next one.

Answer 2

Here is an example of using induction that doesn't use sigma notation.

The OP can put it in their #Education Reference Folder.

Show that

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

Base Case:
True when $n = 1$ since $1 = \frac{1(1+1)}{2}$.

Inductive Step:
Assume that $1 + 2 + \dots + k = \frac{k(k+1)}{2}$.
Then $1 + 2 + \dots + k + (k+1) = (1 + 2 + \dots + k) + (k+1) =\frac{k(k+1)}{2} + (k+1) =$
$\quad (k+1) (\frac{k}{2} + 1) =\frac{(k+1)(k+2)}{2}$

So by induction, $\text{(1)}$ is always true.

Answer 3

Let $F(n)$ and $G(n)$ be algebraic formulas with a free variable $n.$ (That is, neither of them specifies what $n$ is, except we will assume that $n$ must be a number.)

For any $n$ let $S_n$ be the $sentence $ $ F(n)=G(n).$

Suppose the task is to prove that $S_n$ is true for each $n\in \Bbb N. $

For a start, look at $S_1,$ which is $F(1)=G(1).$ This is called the base case. Of course if $F(1)\ne G(1)$ then the task is impossible. If $F(1)=G(1)$ we proceed to what is called the inductive step/part/phase.

We attempt to prove that $S_n\implies S_{n+1}$ for each $n\in \Bbb N.$ This step does not assume that $S_n$ is actually true for any $n.$

( An amusing example: If $F(n)$ is $n$ and $G(n)$ is $n+1$ then $S_n$ is $n=n+1$ and $S_{n+1}$ is $n+1=n+2,$ and we can prove in this example that $S_n\implies S_{n+1}$ even though $S_n$ is never true.)

A very important technique here is to examine how $F(n)$ is related to $F(n+1)$ and how $G(n)$ is related to $G(n+1).$ For example what is $F(n+1)-F(n)$? In some Q's we examine $F(n+1)/F(n)$.

With regards to $F(n+1)-F(n)$: If $S_n$ is true then $F(n)=G(n),$ which implies the following sentence: $$S_{n+1}\iff F(n+1)=G(n+1) \iff$$ $$\iff F(n+1)-F(n)=G(n+1)-F(n)\iff $$ $$\iff F(n+1)-F(n)=G(n+1)-G(n).$$ In many Q's the formulas $F(n+1)-F(n)$ and $G(n+1)-G(n)$ are much simpler than the formulas $F(n)$ and $G(n).$ And it might not be hard to prove (without any assumptions about the truth of any $S_n$) that $F(n+1)-F(n)=G(n+1)-G(n)$ for each $n\in \Bbb N.$ If we can, then we do have $S_n\implies S_{n+1}$ for each $n\in \Bbb N.$

Finally we place all this next to the Principle of Induction: If $S_1$ is true and if $S_n\implies S_{n+1}$ for each $n\in \Bbb N,$ then $S_n$ is true for each $n\in \Bbb N.$

Example: $F(n)=\sum_{j=1}^nj^3$ and $G(n)=(n(n+1)/2)^2.$ We check that $F(1)=1=G(1).$ Now for any $n\in \Bbb N$ we have $$F(n+1)=\sum_{j=1}^{n+1}j^3=(n+1)^3+\sum_{j=1}^nk^3=$$ $$=(n+1)^3+F(n)$$ so $F(n+1)-F(n)=(n+1)^3....$ And $(n+1)^3$ looks simpler than the formula $F(n).$

Now use the definition of $G(n)$ to prove that $G(n+1)-G(n)=(n+1)^3 $ for any $n\in \Bbb N,$ and you're done.

Remark: It has been said that $\sum_{j=1}^nj^3=(n(n+1)/2)^2$ "looks like a mistake", as if someone accidentally wrote the square of the formula for $\sum_{j=1}^nj$ on the RHS (Right Hand Side). But it's correct. E.g. $1^3+2^3+3^3+4^3=100=(1+2+3+4)^2.$