I am just learning about induction proofs. So far I am only familiar with induction equality proofs, and inequality proofs. Such as, for example, prove the sum of the powers of 2 = $2^{n+1} – 1$…
I am confused on the following proof:
The sum of the first n odd squares is $\frac 43 n^3 – \frac 13n$
How do I start this proof? it looks like only one statement with nothing to compare it to. I was thinking maybe I would represent the sum of the first n odd squares as the formula $(2n – 1)^2$ and then set the proof up as
$(2n – 1)^2 = \frac 43 n^3 – \frac 13n$
so it looks more like the form I am used to. Is this correct? Am I missing a small nuance of importance? Thanks for any and all help.
Best Answer
You need to take the sum of the first $n$ odd squares, e.g.if $n=3$, then you need to add $1+9+25=35$. And, that does indeed equal $\frac{4}{3}n^3-\frac{1}{3}n$ for $n=3$: $\frac{4}{3}3^3-\frac{1}{3}3=\frac{4}{3}27-1=36-1=35$
Now, to prove that this is true in general using induction:
Base: $n=0$: $\frac{4}{3}0^3-\frac{1}{3}0=0-0=0$ which is indeed the sum of the first $0$ odd squares. Check!
Step: Assume that for some $k$ the sum of the first $k$ odd squares is $\frac{4}{3}k^3-\frac{1}{3}k$. Now let's consider the sum of the first $k+1$ odd squares, which is of course the sum of the first $k$ odd squares plus the $k+1$-th odd square, which is $(2k+1)^2$. So, by the inductive hypothesis the sum is $\frac{4}{3}k^3-\frac{1}{3}k+(2k+1)^2$, and now you need to verify that this does indeed equal $\frac{4}{3}(k+1)^3-\frac{1}{3}(k+1)$. Let's see:
$$\frac{4}{3}k^3-\frac{1}{3}k+(2k+1)^2=$$
$$\frac{4k^3-k+3(4k^2+4k+1)}{3}=$$
$$\frac{4k^3+12k^2+12k-k+3}{3}=$$
$$\frac{4k^3+12k^2+12k+4-k+3-4}{3}=$$
$$\frac{4(k^3+3k^2+3k+1)-(k+1)}{3}=$$
$$\frac{4(k+1)^3}{3}-\frac{1}{3}(k+1)$$