Mathematical Induction

>>8543118
>CS majors

it's easy if you know the tricks

>>8543120
lol

>>8543120
H-How did you know?

>>8543123
Which are? I've gotten >=B's in every class, but induction is killing me, and I've been googling it for days.

>>8543129

Not him, but he knew because you're trying to cram induction in 12 hours. Which means you're not a math major, but you have to know proof by induction. So, CS.

Prove the theorem true for the base case

Assume the theorem is true for the n case. Prove that with this assumption the theorem is true for the n+! case.

That's the gist of it.

>>8543134
Isn't induction somewhat a mathematical fallacy since you're proving something based on an assumption?

>>8543136
Think of it as a ladder

We prove it for some base, i.e n = 1

Now we assume n is true and we prove it for n+1

Because we know 1 is true, it follows that 2 is true because we proved it for n+1,

Because we know 2 is true, it follows that 3 is true, and so on and so forth.

It's not a fallacy because you can actually prove that induction is true(had to do it for a class). If you think of it as a ladder it makes more sense. We pick some starting step, then we pick an arbitrary step and show the next step is true. We can then start at the bottom and move up because we know the bottom is true.

>>8543136
b-b-b-brainlet

>>8543136
No.

What you're doing is showing the property holds for a base case. Then you show that the property holds for the n+1 case if it holds for the n case.

Apply the second part of the proof to the base case. Then to the case that results from that, and ect... to infinity.

>>8543118
Get super good in like one hour through cramming.
Assume that you'll still be good at it after n hours.
Hope for the best.

>>8543136
lmfao dude

>>8543729
meta

>>8543136
If you want to get deep into it it relies on axiomatic formalizations of arithmetic that the counting numbers have predictable properties. Lots of brainless morons memeing it up responding to you acting like this is an obvious thing when people like Bertrand Russel wrote whole books on this subject. This is metamathematics topic and is rather unpopular after Godel.

>>8543793
based post

>>8543129
base case will be like two lines. Inductive Hypothesis will be what you want (true for every k) and then just manipulate it to show it is true for k+1

>>8543118
Mathematicians HATE him!
He is a freshman
PROVES LIKE A SOPHOMORE

Local student exposes shocking shortcut to learning proofs by induction. Learn 5$ trick to get good at induction in 12 HOURS.

LEARN THE TRUTH NOW!

>>8543136
not for countably infinite sets

>>8543913
*$5+1

>>8543136
>Isn't induction somewhat a mathematical fallacy since you're proving something based on an assumption?

In some systems (peano arithmetic) induction is an axiom, in our modern mathematics it is a theorem.

Here is the theorem that we call "induction":

Let N be the set of natural numbers.
If the set M contains the first natural number (1 or 0 depending on your construction)
and if for every element of M, its successor is also in M then M=N

Then induction works like this. Suppose you want to prove: Every natural number is bigger than or equal than 0 (for simplicity).

Then let M be the set of all numbers that are bigger than or equal than 0.

Well, 0=0 so 0 must be in M

Then let x be any element of M. That means that x is larger than or equal than 0

then the successor of x is x+1 and x+1 is larger than x, and x is larger than or equal to 0, therefore x+1 is larger than or equal to 0.

Therefore every successor of an element of M, is in M.

Then M=N

So this is true for all natural numbers.

This is the justification. Non mathematicians are obviously allowed to use the babby unrigorous version of this because it is really equivalent so who cares.

>>8543118
trivial

>>8543729
destroyed