I simply don't get mathematic induction and I want to die

[Andrew]

Please. I have read this chapter the entire day and I am about to give up. 

All I see is they doing weird crap. 

So step (1) is plugging in 1 for any n. So far so goo. 

Step (2a) is plugging k for any n. No problem. 

Step (2b) is plugging in (k+1) for any n. And theeeeeeeen whaaaaaat??? What have we freaking achieved with this other than getting a mess of an expression? How is that of any meaning? I don't even understand the algebra they with the plugins and then out of the blue they claim it's all nice and demonstrated. HOW COME? 
 

[Emilia1320]

I can see you are studying induction. 

So, idea here is to show that *if P(n) holds for P(k) it also holds for P(k+1)*. And idea of first step is to prove it to first natural positive integer. When it's proven for 1 according to if P(k) is true also P(k+1) also for 2 it is true. And when 2 is proven according to same thing 3 is true and this continues to infinity.

[Andrew]

1 minute ago, Emilia1320 said:

I can see you are studying induction. 

So, idea here is to show that *if P(n) holds for P(k) it also holds for P(k+1)*. And idea of first step is to prove it to first natural positive integer. When it's proven for 1 according to if P(k) is true also P(k+1) also for 2 it is true. And when 2 is proven according to same thing 3 is true and this continues to infinity.

Hi,

 

Thanks a lot! 

I kind of don't habe time to care about the philosophy behind it. It's mostly the hands on thing that I want to find about. Once you've plugged (k+1) in for every n, what are you supposed to do? 

[~Lc~]

1 hour ago, Andrew said:

Hi,

 

Thanks a lot! 

I kind of don't habe time to care about the philosophy behind it. It's mostly the hands on thing that I want to find about. Once you've plugged (k+1) in for every n, what are you supposed to do? 

The philosophy of it is the answer... it's one of the mathematical concepts which you prove once using an example and then go "proven by mathematical induction"...

 

Please be courteous to those who help you on the forum

[Emilia1320]

2 hours ago, Andrew said:

Hi,

 

Thanks a lot! 

I kind of don't habe time to care about the philosophy behind it. It's mostly the hands on thing that I want to find about. Once you've plugged (k+1) in for every n, what are you supposed to do? 

The answer is in sentence "to prove if P(k) is true also P(k+1) is true"

How, now that depends on question. Generally you'll want to plug in your form for P(k) and add the single term for which (k+1) and show their sum is equal to P(k+1). That is for sum proofs at least, for other types you'll need to figure out something else.

[Rigel]

If you've seen recursion in Computer Science, both concepts mesh in a seamless way. As the above replies suggest, you assume first that the statement P(n) is true (for given n) PROVIDED the base case is true, to then show P(n+1) is true. Simple example, the sum of all numbers i from i=1 to n is n(n+1)/2. Our claim P(n) (statement) will be that the sum is n(n+1)/2 summing up to n. First, for 1 (our base case), we clearly have 1(1+1)/2=1, so base case is true. Else, assume the statement is true for n. Then, we sum:

n+1+(n(n+1)/2)=(n+1)(n+2)/2

Which is our expected formula for n+1. Hence, the statement must hold for all n.This is a very simple case and can get complicated depending on the problem. But hopefully this example illustrates the idea behind induction (you can prove induction holds provided we assume the well-ordering principle, but that's some jazz related to set theory and stuff).

There is a stronger concept called strong induction which is useful (although you won't need it for a course like this), which states that if a statement P(n) is true for all k smaller than n, then P(n+1) is true.

P.S: Emilia said that this holds up to infinity. This is NOT TRUE. It only holds for natural integers (albeit arbitrarily large). It's a subtle point that took me some days to realize. 

Edited May 12, 2016 by Rigel

[Andrew]

I still don't get it, my head just doesn't seem to work in this specific ay. 
I really need no explanation of how to do it, as I've read uncountable times the rationale. 

i just need to know, in my working, how am I supposed to go about? 
I plug the k+1 in every n. Do I expand? Do I move things around? What's the final objective appearance-wise?