1. ## Induction

This post has been moved to a more appropriate place.
Originally Posted by >_<SHY_GUY>_<
Hi, im taking an algebra II course that teaches both Algebra A and B in one semester. one thing i don't understand that we have been going through is proof by induction. i dont get the steps, i dont understand it. here are some equations that we reviewed in which i didn't understand:

1. 2+4+6+8+...+2n= n(n+1)

2. 1+5+9+13+...+(4n-3)= n(2n-1)

3. 3+8+13+18+...+(5n-2)= n/2 (5n+1)

4. 1+2^2+2^3+...+2^n-1= 2^n-1 [^ is used to express in exponents since i dont know how to put it here]

5. 1^3+2^3+3^3+4^3+...+n^3= n^2 (n+1)^2/ 4

i was wondering if you can help me because after the teacher doing these, i could not understand how she got (k+1) in some of the equations and how to use it. i am in dieing need of help and i would greatly appreciate it if you can help me

2. Hello, Shy Guy!

Do you understand the procedure for an inductive proof?

We are given a statement $\displaystyle S(n)$ which is allegedly true for all natural numbers $\displaystyle n.$

. . (1) Verify that statement $\displaystyle S(1)$ is true.

. . (2) Assume that statement $\displaystyle S(k)$ is true.

. . (3) Prove that statement $\displaystyle S(k+1)$ is true.

I'll walk through a couple of these for you . . .

$\displaystyle 1)\;\;2 + 4 + 6 + 8 + \cdots + 2n \:=\:n(n+1)$
(1) Verify $\displaystyle S(1)$ . . . Substitute $\displaystyle n=1.$

We have: .$\displaystyle 2 \:=\:1(1+1)\quad\Rightarrow\quad 2 \:=\:2\quad \hdots\quad \text{true!}$

(2) Assume that: .$\displaystyle 2 + 4 + 6 + 8 + \cdots + 2k \;=\;k(k+1)$

(3) Prove that $\displaystyle S(k+1)$ is true.
The statement looks like this: .$\displaystyle {\color{blue}2 + 4 + 6 + \cdots + 2k +2(k+1) \;=\;(k+1)(k+2)}$
. . [This is what we wish to prove.]

Start with $\displaystyle S(k)\!:\;\;2 + 4 + 6 + \cdots + 2k \;=\;k(k+1)$

Add $\displaystyle 2(k+1)$ to both sides: .$\displaystyle 2 + 4 + 6 + \cdots + 2k + 2(k+1) \;=\;k(k+1) + 2(k+1)$

. . The right side is: .$\displaystyle k(k+1) + 2(k+1) \:=\:k^2 + k + 2k + 2 \:=\:k^2 + 3k + 2 \:=\k+1)(k+2)$

The equation becomes: .$\displaystyle 2 + 4 + 6 + \cdots + 2k + 2(k+1) \;=\;(k+1)(k+2)$

This is $\displaystyle S(k+1)$ . . . The inductive proof is compete!

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

$\displaystyle 5)\;\;1^3 + 2^3 + 3^3 + \cdots + n^3 \;=\;\frac{n^2(n+1)^2}{4}$

(1) Verify $\displaystyle S(1)$ . . . Substitute $\displaystyle n=1.$

We have: .$\displaystyle 1^3\:=\:\frac{1^2(1+1)^2}{4}\quad\Rightarrow\quad 1 \:=\:1\quad \hdots\quad \text{true!}$

(2) Assume that: .$\displaystyle 1^3 + 2^3 + 3^3 + \cdots + k^3 \;=\;\frac{k^2(k+1)^2}{4}$

(3) Prove that $\displaystyle S(k+1)$ is true.
The statement looks like this: .$\displaystyle {\color{blue}1^3 + 2^3 + 3^3 + \cdots + k^3 +(k+1)^3 \;=\;\frac{(k+1)^2(k+2)^2}{4}}$
. . [This is what we wish to prove.]

Start with $\displaystyle S(k)\!:\;\;1^3 + 2^3 + 3^3 + \cdots + k^3 \;=\;\frac{k^2(k+1)^2}{4}$

Add $\displaystyle (k+1)^3$ to both sides: .$\displaystyle 1^3 + 2^3 + 3^3 + \cdots + k^3 + (k+1)^3 \;=\;\frac{k^2(k+1)^2}{4} + (k+1)^3$

. . The right side is: .$\displaystyle \frac{k^2(k+1)^2}{4} + (k+1)^3 \;=\;\frac{(k+1)^2}{4}\,[k^2 + 4(k+1)]$

. . . . $\displaystyle =\;\frac{(k+1)^2}{4}[k^2+4k+4] \;=\;\frac{(k+1)^2(k+2)^2}{4}$

The equation becomes: .$\displaystyle 1^3 + 2^3 + 3^3 + \cdots + k^3 + (k+1)^3 \;=\;\frac{(k+1)^2(k+2)^2}{4}$

This is $\displaystyle S(k+1)$ . . . The inductive proof is compete!