Examples of Strong Induction?

Question

What are some simple examples of problems applying Strong, or Complete Induction, I can use for a class I'm teaching?

Answer 1

Here's my absolute favorite example of strong induction. It was posed to me when I was in the 8th grade at a camp for "gifted kids". I hadn't realized it was strong induction until you asked your question, actually, but it clearly is. I added another example below it that is more traditional.

Scenario:

On an island lived 1,000 very mathematically-inclined natives, 500 of whom had blue eyes and 500 of whom had brown eyes. The natives followed a very peculiar religion, the tenets of which were:

1) It is taboo to discuss one's eye color with ANYONE else under ANY circumstances.
2) Each day, at high noon, all natives must gather at the center of the island in order to silently gaze at each other in the presence of the Oracle (a statue of their god).
3) If any person should ever discover that he has blue eyes, he must commit suicide in the name of the Oracle.

(Also, these natives had no mirrors or reflective surfaces, and the water around the island is quite murky and unreflective as well.)

Because of the daily get-togethers, each and every blue-eyed native on the island saw that, other than himself, there are 499 blue-eyed natives and 500 brown-eyed natives on the island. Likewise, every brown-eyed native saw 500 blue-eyed and 499 brown-eyed natives. No one knew his own eye color, however.

So life proceeded normally until one fateful day at noon, when the Oracle suddenly became animated and spoke the horrible, tragic words: "There are blue-eyed natives on this island!"

Exactly 499 days later, at high noon, every blue-eyed native committed suicide.

So how can giving a piece of information that everyone already knows make such a big difference?

Answer:

Strong induction.

Suppose that there were only one blue-eyed native on the island. He would see that everyone else has brown eyes. When the Oracle said "There are blue-eyed people on this island!", he would immediately conclude that he MUST be the one...and would kill himself on the spot.

Now suppose there were two blue-eyed natives. Each of them would see one other person with blue eyes, so neither would kill himself on the day of the Oracle's pronouncement. However, the NEXT day, seeing that the only other blue-eyed native had not killed himself the day before, each native could then conclude that he had blue eyes, and therefore both would commit suicide on the second day.

...

On the 499th day, each of the 500 blue-eyed natives, seeing 499 other blue-eyed natives who had not killed themselves the previous day, would correctly deduce that he MUST have blue eyes, so each of them commits suicide at the same time.

- - - - -

This one is from my textbook from last semester, Rosen's Discrete Mathematics and its Applications, 5th edition. I picked it because it is solved twice, once with regular induction and once with strong induction.

Prove that every amount of postage of 12 cents or more can be formed using just 4-cent and 5-cent stamps.

REGULAR INDUCTION:

Let P(n) be the statement "Postage of n cents can be formed using 4-cent and 5-cent stamps".

Basis: k = 12

P(12) is true, because 12 cents can be formed using three 4-cent stamps.

Induction:

Assume that P(k) is true, that is, that postage of k cents can be formed using some combination of 4-cent and 5-cent stamps.

Then to form postage of k + 1 cents, there are two possibilities.

1) If any 4-cent stamps were used to get k cents of postage, take one of the 4-cent stamps and replace it with a 5-cent stamp. You now have k + 1 cents of postage.

2) If only 5-cent stamps were used to get k cents of postage, since we know that k ≥ 12, we have at LEAST three 5-cent stamps. (I.e. the smallest k that can only be formed using 5-cent stamps is 15.) So if you replace any three 5-cent stamps with four 4-cent stamps, you will have k + 1 cents of postage.

STRONG INDUCTION:

Basis:

This proof requires 4 basis cases.

k = 12: 12 cents of postage can be formed using three 4-cent stamps.

k = 13: 13 cents of postage can be formed using two 4-cent stamps and a 5-cent stamp.

k = 14: 14 cents of postage can be formed using a 4-cent stamp and two 5-cent stamps.

k = 15: 15 cents of postage can be formed using three 5-cent stamps.

Induction:

For k > 15, assume that we can can form postages of j cents, for every j between 12 and k, inclusive (12 ≤ j ≤ k). Then, to form a postage for k + 1 cents, use the same postage as for k - 3 cents, but add a 4-cent stamp.

Answer 2

Strong Induction Example

Answer 3

it particularly relies upon on what you're allowed to assume. while you're allowed to assume the accepted theory of induction, then enable L be the set of helpful integers m such that each and all and sundry integers from a million to m coated are in ok. Then of course a million ? L, and if n?L, then of course n+a million?L. So each helpful integer is in L, for this reason additionally in ok. For S, evaluate the set of integers for which S_n is real, and practice (a million) to it.