induction

[SNA]

can anyone please explain me in simple words about induction and how to use induction to prove something.

[Rashakil Fol]

can anyone please explain me in simple words about induction and how to use induction to prove something.

Sure. Take a proposition, i.e. a statement that can either be true or false. For example: "For all positive integer values of N, the sum of the first N odd numbers equals N*N."

This can be divided into a set of sub-propositions:
"The sum of the first 1 odd numbers equals 1*1."
"The sum of the first 2 odd numbers equals 2*2"
"The sum of the first 3 odd numbers equals 3*3."
and so on.

Just for the sake of syntax, let's let P(N) represent the proposition, "The sum of the first N odd numbers equals N*N." I.e.
P(1) = "The sum of the first 1 odd numbers equals 1*1."
P(2) = "The sum of the first 2 odd numbers equals 2*2."
P(3) = "The sum of the first 3 odd numbers equals 3*3."
and so on. Each of these are 'propositions', remember, which can be proven either true or false.

Proof by induction is in two parts:
Step 1. Show that your "base case" proposition is true. That is, show that P(1) is true.
Step 2. Take some value M. Show that if the proposition P(M) is true, then the proposition P(M+1) is true.

Let's do this for the above example. First, we follow step 1, which means we need to show that P(1), the statement, "The sum of the first 1 odd numbers equals 1*1," is true. This is pretty trivial: clearly, 1 = 1*1. This completes step 1.

Then we perform step 2. To show that, for any value of M, if P(M) is true, then P(M+1) is true, it suffices to assume that P(M) is true, and then, based on this assumption, prove that P(M+1) is true.

Assume that P(M) is true, for some value of M. This means that the sum of the first M odd numbers equals M*M. That is,

1 + 3 + 5 + ... + (2M - 1) = M*M.

It follows that

1 + 3 + 5 + ... + (2M - 1) + (2M + 1) = M*M + 2M + 1

I.e. after factoring:

1 + 3 + 5 + ... + (2M - 1) + (2(M+1) - 1) = (M + 1)*(M + 1)

The left side of this equation is the sum of the first M+1 odd numbers, and the right side is (M+1)*(M+1). Hence, the statement, "The sum of the first M+1 odd numbers equals (M+1)*(M+1)," is true.

What does this tell us?

From step 1, we know that P(1) is true. From step 2, we know that if P(1) is true, then P(2) is true. Hence, P(2) is true. Then from step 2, we know that if P(2) is true, then P(3) is true. Hence, P(3) is true. And so on and so on, we can show that P(N) is true for any value of N.

[SNA]

Thanks alot wonderful and invested answer well done!