Induction problem in logic?

Question

Prove for all n that exist in N (all natural numbers),
0 squared + 1 squared + 2 squared + ... + n squared =
n(n+1)(2n+1) all divided by 6.

I've gotten to the base case, but after that I'm lost on what to do for the inductive step.

Any help would be greatly appreciated. Thanks.

Answer 1

Base cases: n = 0, 1, 2 all work fine

Prove that it works for n + 1

0^2 + 1^2 + 2^2 + ... + n^2 + ( n + 1 ) ^2 = ( n + 1 ) ( n + 2 ) ( 2 ( n + 1 ) + 1 ) / 6

The left-hand side is

0^2 + 1^2 + 2^2 + ... + n^2 + ( n + 1 ) ^2
n ( n + 1 ) ( 2n + 1 ) / 6 + n^2 + 2n + 1
( n^2 + n ) ( 2n + 1 ) / 6 + n^2 + 2n + 1
( 2n^3 + n^2 + 2n^2 + n ) / 6 + ( 6n^2 + 12n + 6 ) / 6
( 2n^3 + 9n^2 + 13n + 6 ) / 6

the right-hand side is

( n + 1 ) ( n + 2 ) ( 2 ( n + 1 ) + 1 ) / 6
( n^2 + 3n + 2 ) ( ( 2n + 2 ) + 1 ) / 6
( n^2 + 3n + 2 ) ( 2n + 3 ) / 6
( 2n^3 + 3n^2 + 6n^2 + 9n + 4n + 6 ) / 6
( 2n^3 + 9n^2 + 13n + 6 ) / 6

They are the same.

Answer 2

Suppose [k=0, n]∑k² = n(n+1)(2n+1)/6. Then:

[k=0, n+1]∑k²
= [k=0, n]∑k² + (n + 1)²
= n(n + 1)(2n + 1)/6 + (n + 1)²
= (n(2n + 1)(n + 1) + 6(n + 1)(n + 1))/6
= ((2n² + n)(n + 1) + (6n + 6)(n + 1))/6
= (2n² + 7n + 6)(n + 1)/6
= (2n + 3)(n + 2)(n + 1)/6
= (2(n + 1) + 1)((n + 1) + 1)(n + 1)/6

Which is precisely what we would obtain by substituting n+1 into the formula. Thus if it holds for n, it holds for n+1, and by induction, for all n. Q.E.D.

Answer 3

The rest of the proof should take the following form:

Inductive Hypothesis: (IH) Suppose that 1^2+...+(n-1)^2 = (n-1)(n)(2n-1) / 6.

Then we want to show that 1^2+...+(n-1)^2+n^2 = n(n+1)(2n+1)/6. From IH we know that
1^2+....+(n-1)^2+n^2 = (n-1) (n) (2n-1)/6 + n^2.

You should be able to finish the proof from here.

Answer 4

p(n): 1^2+...+n^2 =n(n+1)(2n+1)/6

suppose p(n) is true and let us prove
p(n+1): 1^2+...+n^2+(n+1)^2= (n+1)(n+2)(2n+3)/6

Since p(n) is true, we can add (n+1)^2 in left hand and right hand of p(n):
1^2+...+n^2+(n+1)^2 =n(n+1)(2n+1)/6 + (n+1)^2 (*)

But
n(n+1)(2n+1)/6 + (n+1)^2 = (n+1)(n+2)(2n+3)/6 (**)
(check!)
hence
(*) and (**) imply p(n+1) is true

Therefore p(n) ---> p(n+1) is true

Since you already proved the base case, the induction is complete.