Member Avatar for SNA

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

  • 2 Contributors
  • 2 Replies
  • 411 Views
  • 2 Days Discussion Span
  • Latest Post Latest Post by SNA

Dani AI

Generated

As has shown, induction is the method that proves a statement for every natural number by (1) checking a base case and (2) showing an arbitrary true case forces the next one. The following clarifications fill common gaps and make writing induction proofs less error-prone.

A compact proof template:

  1. Specify the property P(n) and the exact domain (n >= n0).
  2. Prove the base case(s): P(n0) (and P(n0+1), ... if the step needs them).
  3. State the inductive hypothesis clearly: assume P(k) holds for an arbitrary k >= n0.
  4. Prove P(k+1) using only the hypothesis and valid algebraic/logical steps.
  5. Conclude P(n) holds for all n >= n0 by the principle of induction.

Common pitfalls and practical tips: do not assume P(k) for some specific k — the hypothesis must be for an arbitrary k. If the inductive step gets stuck, try rewriting P(k+1) in terms of P(k) plus an "extra" term, or prove a small auxiliary lemma that supplies the missing piece. When the step requires more than P(k) (for example, recurrence relations that use earlier two values), use strong induction (assume P(1),...,P(k) to prove P(k+1)) or add the extra base cases. Induction applies to any well-ordered set and to recursively defined structures (structural induction), but it does not apply directly to real numbers or non-well-ordered domains.

A short, different example: to prove 1 + 2 + ... + n = n(n+1)/2, take P(n) as that equality, check P(1), assume P(k), then compute 1+...+(k+1) = [k(k+1)/2] + (k+1) = (k+1)(k+2)/2, which is P(k+1); hence the formula holds for all n >= 1.

Recommended Answers

All 2 Replies

Member Avatar for 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.

Member Avatar for SNA

Thanks alot wonderful and invested answer well done!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.