Originally Posted by

**oldguynewstudent** I find that I am confused by strong induction.

I thought I understood it, but now I'm not sure if I have this correct.

Prob: Prove that all postages of $0.20 and more can be formed using only 5 cent and 6 cent stamps.

*Do I list all these in the basis step, or should P(21), P(22), P(23), and P(24) be listed in the induction step?*

Basis step: P(20): A postage of 20 cents can be formed using 5 cent and 6 cent stamps. Four 5 cent stamps = 20 cents, so P(20) is true.

P(21): A postage of 21 cents can be formed using 5 cent and 6 cent stamps. Three 5 cent and one 6 cent stamps = 21 cents so P(21) is true.

P(22): A postage of 22 cents can be formed using 5 cent and 6 cent stamps. Two 5 cent and two 6 cent stamps = 22 cents, so P(22) is true.

P(23): A postage of 23 cents can be formed using 5 cent and 6 cent stamps. One 5 cent and three 6 cent stamps = 23 cents, so P(23) is true.

P(24): A postage of 24 cents can be formed using 5 cent and 6 cent stamps. Four 6 cent stamps = 24 cents, so P(24) is true.

Inductive step: A postage of n cents can be formed using 5 and 6 cent stamps for 20 <= n <= k, k >= 24.

We need to prove that if k postage can be formed, then k+1 postage can be formed using just 5 and 6 cent stamps.

For the k+1 postage, note that with k >= 24, we have P(k - 4) to be true.

Add one 5 cent stamp to k - 4 and we have proved k + 1.

Since the basis step is true and the inductive step are true, the original statement is true by strong MI.

*Please tell me if the stucture, process, and conclusions are valid.*

*Thanks*