Proof by induction (of an algebraic sequence)

Hey all,
Having not studied proof by induction before now, I'm a bit confused at the moment (and have an exercise sheet with 9 statements to prove via induction)

One of the questions (which won't be marked, but is there for practise, etc) is:

Prove by induction that the proposition is true for all positive integers n:

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

I know the theory behind induction (show it's true for P(1), then assuming P(K) is true, prove for P(K+1) etc), I'm just getting stuck with how to get things going? I.e. I can write out everything, but can't see how to prove that P(K+1) is true?

Any help would be awesome :smile:

Thanks,
Tristan

Reply 1

benwellsday

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

This is the sum for P(k). This is assumed to be true. Now using this show P(k+1) is true.

Hint

Spoiler

Reply 2

sonofdot

\displaystyle\sum_{r=1}^{k+1} r^2 = \displaystyle\sum_{r=1}^{k} r^2 + (k+1)^2

You can assume that

\displaystyle\sum_{r=1}^{k} r^2 = \frac{1}{6}n(n+1)(2n+1)

, so substitute that in and try and factorise it to get the desired result :smile:

Reply 3

tristanperry

Hey both,
Thanks for the replies.

I feel really stupid because I'm still not really getting this.

On the RHS (when P(K+1)) I get:

\frac{(k(k+1)(2k+1))}{6}+ (k+1)^2[br][br]=[br][br](k(k+1)(2k+1)+6(k+1)^2) /6 [br]

Although I can't see how to get that back to:

\frac{k(k+1)(2k+1)}{6}

to make the proof complete? Probably a simple algebraic tip I'm forgetting (I hope :wink:

)

Thanks,
Tristan

Reply 4

benwellsday

tristanperry

\frac{k(k+1)(2k+1)}{6}

You don't want it in that form, you want that form but for each k you substitute k+1.

Spoiler

Reply 5

tristanperry

I understand that (sort of), although what do I need to show it as then (i.e. to prove it)?

And if I need to sub (K+1) in then why would I need to add

(k+1)^2

to both sides?

Sorry, but am getting confused.

Reply 6

Sanjetti

benwellsday

You don't want it in that form, you want that form but for each k you substitute k+1.

Spoiler

Indeed.

Reply 7

Sanjetti

tristanperry

I understand that (sort of), although what do I need to show it as then (i.e. to prove it)?

And if I need to sub (K+1) in then why would I need to add

(k+1)^2

to both sides?

Sorry, but am getting confused.

So that you can prove that it is true for n=k+1. You are in essence setting up the dominos so you can knock them over for induciton.

Once you get to 1/6k(k+1)(2k+1) + (k+1)2, take 1/6(k+1) out as a factor and factorise. :smile:

Reply 8

Sanjetti

1/6(k+1)(k(2k+1) + 6(k+1))

Reply 9

tristanperry

Ahh okay, thanks. I *think* I get this (more :P) now :smile:

So I have to effectively show that:

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

Is equal to:

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

For the proof to work?

Reply 10

Sanjetti

tristanperry

Ahh okay, thanks. I *think* I get this (more :P) now :smile:

So I have to effectively show that:

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

Is equal to:

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

For the proof to work?

Exactly. And then you have to show that the equation 1/6n(n+1+(2n+1) is true for n=1, thereby proving that the formula works for n is greater or equal to 1. (This is the easy bit :smile:

)

Reply 11

tristanperry

Brilliant, thanks Sanjetti :smile:

Now that I got the overall concept, it should be easy now. Thanks again to everyone for the help :smile:

Reply 12

Sanjetti

tristanperry

Brilliant, thanks Sanjetti :smile:

Now that I got the overall concept, it should be easy now. Thanks again to everyone for the help :smile:

Np mate

Yeah it definitely gets a lot easier, and they're really satisfying I find! Ok, I just realised how geeky that sounded :biggrin:

Reply 13

tristanperry

Hehe no worries, I know what you mean :wink:

And yeah, I'm sure it will be satisfying when I get it complete :smile:

It's a sheet of 9 questions (3 of which will be marked - not including this question), although probably once I get things "rolling" everything will come fairly easily (that's the hope, anyway :wink: