Question

Prove by induction

N
E i = (N(N+1))/2
i = 0

Answer 1

Have you done proofs via induction before?

Answer 2

\[\sum_{i=0}^{N} i = \frac{ N(N+1) }{ 2 }\] That should be more clear.

Answer 3

Yeah, got it.

Answer 4

So have you done proofs via induction before? Because they can seem pretty weird before you get used to them...

Answer 5

A little bit, I've seen a couple youtube videos, but those are not like this one.

Answer 6

Have you ever done Logic before?

Answer 7

No

Answer 8

Well, there's one type of argument form called "modus ponens" (you don't have to know that) that helped me learn Induction.

It goes like this:
If P, then Q
P
Therefore, Q

Answer 9

Oh, yes then. Sorry.

Answer 10

That looks familiar is what I mean

Answer 11

So, as an example, I might say something like:

If it's raining, then I'll go to bed.
It's raining.

And with those two statements, you can conclude that:

I'm going to bed.

You with me?

Answer 12

Yup

Answer 13

Well, that's one way you can look at Induction (and, I'm mentioning it because it was how things started to click with me regarding Induction).

Answer 14

So it goes something like this:

"Let's just assume for a minute that the sum of the first "k" positive whole numbers is equal to k(k+1)/2."

That's all you're doing, just assuming that it is true.
Then, that would mean that the sum of the first k+1 numbers is equal to:

\[= \frac{ k(k+1) }{ 2 } + (k+1)\]

Answer 15

With me?

Answer 16

Yes, I think so

Answer 17

Now, just factor out the "k+1":
\[= (k+1)(\frac{ k }{ 2 }+1)\]
Which can be simplified further as:
\[= \frac{ (k+1)(k+2) }{ 2 }\]

Answer 18

And that's the exact same form of the equation we started with--the only difference is that that is for the sum of the first "k+1" positive integers and not "k".

That's the "If P, Then Q" part I was talking about--you show that if you assume it's true for the first "k" numbers, then it also must be true for "k+1" numbers.

Once you've gotten that, the rest is easy. You just show that it's true when k=1, which is obvious because the sum of the first "1" positive whole numbers is, of course, 1, and when you plug in "1" into your initial formula you get:

\[\frac{ 1(1+1) }{2 }= 1\]

And that's your "P" part.

Answer 19

Thus, you've proven two steps:

1.) If it's true for n=k, then it's true for n=k+1
2.) it's true for n=1.

And all at once you've proven that that formula is true for EVERY SINGLE POSITIVE INTEGER.

Answer 20

Ok, that helped! thank you :)

Answer 21

Ok, hope that makes sense--don't feel bad if it's still a little foggy (you wouldn't believe how long it took me to get a hang of Induction...). Good luck!