I can do algebra, but I can't prove this properly (and formally)

[flyingpig]

Homework Statement

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

 

[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.

 

[SammyS]

Homework Statement

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

$\displaystyle S(n) : \frac{n(n + 1)(2n + 1)}{6}$ This isn't a part of the Base Step. Use this to define S(n) as the sum of the squares of the first n positive integers.

[STRIKE]Assume[/STRIKE] Show it is true for n = 1: You don't 'assume' this is true, you 'Show' that it's true.

$$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}$$
...
$$= (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"? Yes. At least it is here, and off-hand, I can't think of a case where it's not OK. ... but why not use the language used in the statement of the problem?

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

(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.

 

[Mark44]

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.

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

 

[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

 

[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.

 

[flyingpig]

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

 

[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.