can someone explain what mathematical induction is?

Question

i read my pre-cal textbook and googled mathematical induction examples. and i still dont' understand.
i understood one part where i have to add (k+1) on LHS.
ugh... that's so far i can understand.
i have a test tomorrow morning and i still don't get it. my professor explained but have no clue!

Answer 1

Induction is where you show a statement is true for n = 1, then assume it is true for n = k, and using this assumption, prove it true for n = k+1.

There are three main types of induction, they are all pretty different. Maybe http://en.wikipedia.org/wiki/Mathematical_induction ?

Answer 2

Explain Mathematical Induction

Answer 3

Mathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite sequence of statements is true, then so is the next one.

The method can be extended to prove statements about more general well-founded structures, such as trees; this generalization, known as structural induction, is used in mathematical logic and computer science. The validity of mathematical induction is logically equivalent to the well-ordering principle.

Mathematical induction should not be misconstrued as a form of inductive reasoning, which is considered non-rigorous in mathematics. (See Problem of induction.) In fact, mathematical induction is a form of deductive reasoning and is fully rigorous.

Answer 4

OK so the three steps of induction are:

1) Make sure the thing you want to prove works for a base case. Generally this base case is when you plug in 1.
2) Assume the thing you want to prove works for some general case k. This is called the inductive hypothesis, and you can use this anytime else in your proof.
3) Prove that the right result comes from plugging in the case k+1.

Reason this works:

Well you have your base case that works, and you know that if it works for k, it works for k+1. Therefore, if your base case was 1, it has to work for 2, and 3, and 4, and 5, and.... for all numbers!

EXAMPLE:

Prove: (isin(x)+cos(x))^n = isin(xn)+cos(xn) for an integer n.

Try the base case first: n=1. We have

(isin(x)+cos(x))^1
=isin(1*x)+cos(1*x)

This is obviously true. Our base case is complete.

Now, assume that

(isin(x)+cos(x))^k
=isin(kx)+cos(kx)

This is now true for the purposes of our proof. Next, let's try k+1. We see that

(isin(x)+cos(x))^(k+1)

= (isin(x)+cos(x))*(isin(x)+cos(x))^k

This is where we use our inductive hypothesis (step 2):

= (isin(x)+cos(x))*(isin(kx)+cos(kx))

= -sin(x)sin(kx)+cos(x)cos(kx)
+isin(x)cos(kx)+icos(x)sin(kx)

= cos(x)cos(kx)-sin(x)sin(kx)
+i(sin(x)cos(kx)+cos(x)sin(kx))

=cos(x+kx)+isin(x+kx)

=cos((k+1)x)+isin((k+1)x)

Hey! It works for k+1! We plugged in n=k+1 and we got out just what we wanted, using the inductive hypothesis. Our proof is complete.

I hope the example wasn't beyond what you've learned... but if you don't know, i is the square root of -1, so i^2=-1.

=)