# Homework Help: I can do algebra, but I can't prove this properly (and formally)

1. Sep 14, 2011

### flyingpig

1. The problem statement, all variables and given/known data

Prove that for every integer $$n\geq1$$, that

$$1^2 + 2^2 + ... + n^2 = \frac{n(n + 1)(2n + 1)}{6}$$

2. The attempt at a solution

Note that everything after this sentence are what I am going to write in my assignment to hand in.

(1) Base Case

$$S(n) : \frac{n(n + 1)(2n + 1)}{6}$$

Assume it is true for n = 1

$$S(1) : \frac{1(1 + 1)(2 + 1)}{6} = 1 = 1^2$$

Which is true

(2) Inductive Step, let n = k + 1, then

$$S(k + 1) : \frac{(k + 1)(k + 2)(2k + 3)}{6}$$

$$1^2 + 2^2 + ... + k^2 + (k + 1)^2 = \frac{k(k + 1)(2k + 1)}{6} + (k + 1)^2$$

$$= \frac{k(k + 1)(2k + 1)}{6} + \frac{6(k + 1)^2}{6} = \frac{k(k + 1)(2k + 1) + 6(k + 1)^2}{6}$$

$$= (k + 1)\frac{k(2k + 1) + 6(k + 1)}{6} = \frac{k + 1}{6} (2k^2 + 7k + 6) = \frac{k + 1}{6} (k + 2)(2k + 3) = \frac{(k + 1)(k + 2)(2k + 3)}{6}$$

Therefore by Principles of Mathematical Induction, $$1^2 + 2^2 + ... + n^2 = \frac{n(n + 1)(2n + 1)}{6}$$ is true for all integers $$n\geq1$$

Q.E.D

Questions

a) Is it okay to say "all" instead of "every"?

b) Yeah I will try to line it up in my real assignment, but I couldn't figure out how to do it here.

c) DO I have to put that Q.E.D thing to look smart?

d) Did I do it correctly or did I totally embarrassed myself

2. Sep 14, 2011

### yenchin

Ideally you would want to clearly exhibit that your S(k+1) does indeed have the same form as S(k). So I would add at your very end that

Thus if S(k)=k(k+1)(2k+1)/6, then we also have S(k+1)=(k+1)[(k+1)+1][2(k+1)+1]/6. So by induction the statement is true.

3. Sep 15, 2011

### SammyS

Staff Emeritus
(c): If your professor wants you to use "Q.E.D.", then use it. I've also seen lowercase q.e.d., as well as QED and qed. Also symbols: □ or ■ . What really makes you look smart is a solid proof.

(d): In general the proof looks pretty good, particularly if you're fairly new to doing proofs.

For the inductive step:
Make it clear that you are assuming that your expression is true for n = k and from that you are showing that it's true for n = k+1.

In the problem you posted here, I would write something like:
Inductive Step: Assuming that, $\displaystyle S(k)=\frac{k(k + 1)(2k + 1)}{6}\,,$ show that $\displaystyle S(k+1)=\frac{(k+1)(k + 2)(2k + 3)}{6}\,.$

Proof:
$\displaystyle S(k+1)=S(k)+(k+1)^2$

$\displaystyle =\frac{k(k + 1)(2k + 1)}{6}+(k+1)^2$
...

$\displaystyle =\frac{(k+1)(k + 2)(2k + 3)}{6}\,.$

...​

Many, if not most, students have trouble with inductive proofs. They tend to assume the thing that they should be proving. You have done a good job avoiding that here.

4. Sep 15, 2011

### Staff: Mentor

Here Sammy is telling you the same thing I said earlier and in another thread.

5. Sep 15, 2011

### flyingpig

1) Base Case

$$S(n) : \frac{n(n + 1)(2n + 1)}{6}$$

Let n =1

$$S(1) : \frac{1(1 + 1)(2 + 1)}{6} = 1 = 1^2$$

Which is true

(2) Inductive Step,

Assume that $$S(n) : \frac{n(n + 1)(2n + 1)}{6}$$ is true, then let n = k + 1 [This is my inductive hypothesis?]

$$S(k + 1) : \frac{(k + 1)(k + 2)(2k + 3)}{6}$$

$$1^2 + 2^2 + ... + k^2 + (k + 1)^2 = \frac{k(k + 1)(2k + 1)}{6} + (k + 1)^2$$

$$= \frac{k(k + 1)(2k + 1)}{6} + \frac{6(k + 1)^2}{6} = \frac{k(k + 1)(2k + 1) + 6(k + 1)^2}{6}$$

$$= (k + 1)\frac{k(2k + 1) + 6(k + 1)}{6} = \frac{k + 1}{6} (2k^2 + 7k + 6) = \frac{k + 1}{6} (k + 2)(2k + 3) = \frac{(k + 1)(k + 2)(2k + 3)}{6}$$

Therefore by Principles of Mathematical Induction, $$1^2 + 2^2 + ... + n^2 = \frac{n(n + 1)(2n + 1)}{6}$$ is true for all integers $$n\geq1$$

Q.E.D

6. Sep 16, 2011

### yenchin

Your induction hypothesis is what you assume (after all hypothesis means some sort of guess), i.e. your assumption that S(k)=k(k+1)(2k+1)/6.

So to prove a statement on S(n), you need to

1. Establish the base case, i.e. check S(1).
2. Assume S(k) is true. This is your induction hypothesis.
3. Show that if S(k) is true, then S(k+1) is true.

7. Sep 18, 2011

### flyingpig

Guys for my inductive hypothesis, do I need to state that $$n \in \mathbb{Z}$$ and $$n \geq 0$$

8. Sep 18, 2011

### ArcanaNoir

n is really just a natural number. instead of worrying about writing n is an element of z greater than or equal to 1, just say it's a natural number.

When you write the beginning part, you should put what S(n) is, 1^2 + 2^2 + 3^2.. n^2
e.g say
Prove that $1^2 + 2^2 + 3^2.. n^2 = \frac{n(n + 1)(2n + 1)}{6}$

Then you show it for n=1, like you did.

Now, change your n's to k's. You need to write:
Assume it is true for n=k, that is, assume $1^2 + 2^2 + 3^2.. k^2 = \frac{k(k + 1)(2k + 1)}{6}$

Then, for k+1, $1^2 + 2^2 + 3^2.. (k+1)^2 = \frac{(k+1)(k + 2)(2(k+1) + 1)}{6}$

Then show it like you did.

I like the QED. My prof used to always write, Therefore, by the PMI, the proof is over.

QED sounds better than "the proof is over" in my opinion.