The Student Room Group
Competition - post a photo you've taken of nature >>
Competition - post a photo you've taken of nature >>
Competition - post a photo you've taken of nature >>

Strong Induction?

I know normal induction. Can anyone please explain or give a link to good website which explains strong induction?
Reply 1
Avatar for steve10
steve10
7
Let P(n) be some expression.

In normal induction, you say something like, "If P(n) is true then so also is P(n+1)"
In strong induction you would say, "If P(k), k= 1 to n, are true, then so also is P(n+1)"

In strong induction, you would have a situation where there are multiple instances of an expression being true, and that these lead to the n+1 th instance being true also.
Reply 2
Avatar for tleave2000
tleave2000
4
I'm really no expert so I'd be happy to be corrected, but this is what I've picked up from reading wiki. In plain induction you first have to prove a base case, P(n) where n would usually equal zero. Then you also have to prove that if P(m) is true then P(m+1) is also true and that proves P(x) for any positive integer value of n (ie the natural numbers).

But in strong (aka complete) induction, the inductive step includes an implication that all smaller values as well as larger values are true, so there's no need to separately state the base case.

They also put it in this way, paraphrasing: that in strong induction, the inductive case corresponds to the base case as well.

It's as if the inductive step simultaneously proves the inductive step and the base case. I'm afraid I can't give an example because frankly, I didn't understand any of them : )

Can anyone else give a nice example?
(edited 12 years ago)
Original post by tleave2000
I'm really no expert so I'd be happy to be corrected, but this is what I've picked up from reading wiki. In plain induction you first have to prove a base case, P(n) where n would usually equal zero. Then you also have to prove that if P(m) is true then P(m+1) is also true and that proves P(x) for any positive integer value of n (ie the natural numbers).

But in strong (aka complete) induction, the inductive step includes an implication that all smaller values as well as larger values are true, so there's no need to separately state the base case.

They also put it in this way, paraphrasing: that in strong induction, the inductive case corresponds to the base case as well.

It's as if the inductive step simultaneously proves the inductive step and the base case. I'm afraid I can't give an example because frankly, I didn't understand any of them : )

Can anyone else give a nice example?

The most simple example I seem to remember is the following (do try it by yourself first before opening the spoiler):

Let the sequence aia_i be defined by an=an−1+an−2+an−3,a_n=a_{n-1}+a_{n-2}+a_{n-3}, a1=1,a_1 = 1, a2=2,a_2=2, a3=3a_3=3.

Prove, by strong induction, that the relation an<2na_n<2^n holds ∀n∈Z+\forall n\in \mathbb{Z}^+.

Spoiler

(edited 12 years ago)
Reply 4
Avatar for DFranklin
DFranklin
18
Original post by tleave2000
I'm really no expert so I'd be happy to be corrected, but this is what I've picked up from reading wiki. In plain induction you first have to prove a base case, P(n) where n would usually equal zero. Then you also have to prove that if P(m) is true then P(m+1) is also true and that proves P(x) for any positive integer value of n (ie the natural numbers).

But in strong (aka complete) induction, the inductive step includes an implication that all smaller values as well as larger values are true, so there's no need to separately state the base case.

They also put it in this way, paraphrasing: that in strong induction, the inductive case corresponds to the base case as well.This isn't the important part of strong induction and I'm not entirely sure why they say it. If you want to be pedantic, it's true, but in practice you'll still end up needing to consider some base cases (you just do it as part of proving the inductive step). (If you look at the example they give, it explictly says "To complete the proof, the identity must be verified in the two base cases n = 0 and n = 1.").

They key point is that you're assuming the statement is true for all smaller values of n; this gives you more "material to work with" when proving the inductive step, which is often useful (see both the Wiki example and Farhan's: it's not enough to know the statement is true for n, you need to know it's true for n-1 and n-2 as well).
(edited 12 years ago)

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you