Discrete Math Question ( not really homework) about strong induction

In summary, the conversation discusses the use of strong induction to prove results for combinations of 3-dollar and 10-dollar bills. Two examples are given, one for finding all possible dollar amounts and the other for proving that all amounts of postage of 12 cents or more can be formed using only 4-cent and base case stamps. The main difference between strong and weak induction is that strong induction allows for assuming a statement is true for all values less than or equal to n, while weak induction only considers the statement to be true for n.
  • #1
geforce
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.
 
Physics news on Phys.org
  • #2
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 to Discrete Math Question ( not really homework) about strong induction

1. What is strong induction?

Strong induction is a proof technique used in discrete mathematics to show that a statement is true for all natural numbers greater than or equal to a base case. It is similar to mathematical induction, but instead of just considering the previous case, it also considers all previous cases.

2. How does strong induction differ from regular mathematical induction?

In regular mathematical induction, the proof only considers the previous case. However, in strong induction, the proof considers all previous cases. This means that strong induction is more powerful and can be used to prove more complex statements.

3. When should strong induction be used instead of regular mathematical induction?

Strong induction should be used when the statement to be proven depends on multiple previous cases, rather than just one previous case. It is also useful when there is no clear starting point for the proof.

4. Can strong induction be used to prove statements about other mathematical objects, such as graphs or sets?

Yes, strong induction can be applied to any mathematical object that has a natural ordering. This includes graphs, sets, and other discrete structures.

5. Are there any limitations to strong induction?

Strong induction can only be used to prove statements about natural numbers or other objects with a natural ordering. It cannot be used for continuous objects, such as real numbers. Additionally, strong induction can only be used for statements that can be broken down into finite cases.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
3K
  • Calculus and Beyond Homework Help
Replies
5
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
2K
  • Calculus and Beyond Homework Help
Replies
13
Views
3K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
2K
  • Calculus and Beyond Homework Help
Replies
5
Views
432
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
3K
Back
Top