1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, I would be representing it as a summation notation containing (2i - 1)^2 $\endgroup$ – Conner May 18 '17 at 1:17
  • $\begingroup$ I think $(2n+1)^2$ is better but not sure if it matters. $\endgroup$ – marshal craft May 18 '17 at 1:18
2
$\begingroup$

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)$$

$\endgroup$
  • 1
    $\begingroup$ @Conner You're welcome! Please note that I had a small mistake in my earlier answer ... The $(k+1)$-th odd square is $(2k+1)^2$, and not $(2k-1)^2$, which is what I had first. $\endgroup$ – Bram28 May 18 '17 at 1:34
  • $\begingroup$ Thank you. Just one more clarity question. Specifically when you are constructing your Induction Hypothesis, I was under the impression from earlier proofs I've done that we would have to insert K + 1 into (2k + 1)^2, making it (2(k + 1))^2 = (2k + 3)^2, and then we would add that. Is that not true in this case? $\endgroup$ – Conner May 18 '17 at 2:01
  • 1
    $\begingroup$ @Conner The $k$ -th odd square is $(2k-1)^2$, and so the $(k+1)$-th odd square is $(2(k+1)-1)^2=(2k+1)^2$. So yes, you do fill in $k+1$ for $k$, but you have to choose the right formula! :) $\endgroup$ – Bram28 May 18 '17 at 2:09
  • $\begingroup$ Ahh. Yes I see. I was very confused for a moment because I changed my entire representation of the summation of the odd squares to (2n+1)^2 instead, so I could account for the base n = 0. It didn't even cross my mind that you were just showing the example of if I had kept it (2n-1)^2. This has really helped my comprehension the induction proof process to me though. I appreciate you answering back. $\endgroup$ – Conner May 18 '17 at 2:13
0
$\begingroup$

I will give an alternative method to prove the claim.

It's a standard exercise in induction to show that \begin{align} \sum^{2N}_{n=1} n^2 = \frac{2N(2N+1)(4N+1)}{6}. \end{align} Next, observe \begin{align} \sum_{n \text{ even}}+\sum_{n\text{ odd}} n^2 =& \sum^N_{k=1} (2k)^2+\sum_{n \text{ odd}}^{2N}n^2\\ =& 4\sum^N_{k=1}k^2 + \sum_{n \text{ odd}} n^2\\ =&\ \frac{4N(N+1)(2N+1)}{6}+\sum_{n \text{ odd}} n^2. \end{align} Hence it follows \begin{align} \sum_{n \text{ odd}}^{2N} n^2 =&\ \frac{2N(2N+1)(4N+1)}{6}- \frac{4N(N+1)(2N+1)}{6}\\ =&\ \frac{4N^3-N}{3} \end{align}

Now, use induction to prove the above formula holds if you like.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.