Question

1. Use strong induction to show that if you can run one mile or two miles, and if you can always run two more miles once you have run a specified number of miles, then you can run any number of miles.

Answer 1

Proof

Explanation:

Given:

- If you run 1 or 2 miles

- You can always run 2 miles more after running specified number of miles

Find:

- Prove that you can run any number of miles

Solution:

- Let M ( n ) be " You can run the nth mile"

Basis step: n = 1 and n = 2

- M(1) and M(2) are True, because you can run one or two miles as given in statement.

Inductive Step:

- We assume that M(1) , M(2), ......, M( k ) are all true, thus you can run the first k miles.

- We then need to prove that M ( k+ 1 ) is also true.

- Since M ( k - 1 ) is true then M ( k + 1 ) is true. ( You can always run 2 miles more after running specified number of miles )

Conclusion:

- By the principle of strong induction, M ( n ) is true for all positive n integers.