Discrete Math Question ( not really homework) about strong induction

  • Thread starter geforce
  • Start date
  • #1
26
0
For some questions strong induction would test for cases n+1, n+2 and for other n+1,n+2,n+3, or other ways, why is that? Here's two examples


Suppose that the only paper money consists of 3-dollar bills and 10-dollar bills. Find what dollar amounts
can be made from a combination of these bills. Prove your result.
SOLUTION: Clearly the amounts $3, $6, $9, $10, $12, $13, $15, $16, $18 can all be made using 3-dollar bills and 10-dollar bills. In addition any amount greater than $17 be made as well. To prove this we use strong induction.
Base case: $18 can be made from 6 3-dollar bills, $19 can be made from one 10-dollar bill and three 3-dollar
bills. And of course, $20 can be made from two 10-dollar bills.

and the other example,

prove that every amount of postage of 12 cents or more can be formed using just 4-cent and

base case

we can form postage of 12, 13 ,14 ,15 cents using three 4-cent stamps, two 4- cents stamps ... etc this shows that P(12),P(13), P(14) and P(15) are true.
 

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,833
964
It is never necessary to "test for n+1, n+2, ...". You need to show a statement is true for n= 0, then show "if the statement is true for all [itex]k\le n[/itex] then it is true for n= k+1".

(The difference between "strong induction" and "weak induction" is that strong induction allows you to assume "true for all [itex]k\le n[/itex]" while weak induction uses only "true for k= n".)
 

Related Threads on Discrete Math Question ( not really homework) about strong induction

Replies
1
Views
1K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
1
Views
891
  • Last Post
2
Replies
26
Views
3K
  • Last Post
Replies
4
Views
8K
Replies
7
Views
5K
Replies
5
Views
1K
  • Last Post
Replies
3
Views
908
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
6
Views
1K
Top