Question

Proof by Strong Induction Every amount of postage that is at least 12 cents can be...

  1. Proof by Strong Induction

Every amount of postage that is at least 12 cents can be made from 4-cent and 5-cent stamps.

1) Base case:

2) Inductive hypothesis:

3) Inductive proof:

  1. Given the definition of function f:

f(0) = 5

f(n) = f(n-1) + 3n

What is f(3) ?

What is closed-form solution for f(n) (no need to proof)?

Hint: try to write a couple of first values without any calculations – f(1)=f(0)+3n=5+3*1, f(2) = f(1)+3*2=5+3*1+3*2, f(3)=… to see the rule

Math   Advanced-Math   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1


0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
please use strong induction to Prove that every amount of postage of 12 cents or more...
please use strong induction to Prove that every amount of postage of 12 cents or more can be formed using just 5-cent and 6-cent stamps.
Using strong induction, prove that any postage greater than equal to 28 cents can be formed...
Using strong induction, prove that any postage greater than equal to 28 cents can be formed using only 8-cent and 5-cent stamps?
7. (Problem 3 on page 341 from Rosen) Let P(n) be the statement that a postage...
7. (Problem 3 on page 341 from Rosen) Let P(n) be the statement that a postage of n cents can be formed using just 3-cent stamps and 5-cent stamps. The parts of this exercise outline a strong induction proof that P(n) is true for n ³ 8. Show that the statements P(8), P(9), and P(lO) are true, completing the basis step of the proof. What is the inductive hypothesis of the proof? What do you need to prove in the...
Please show all the steps..thankyou Use strong induction to show any amount of postage ≥ ___________...
Please show all the steps..thankyou Use strong induction to show any amount of postage ≥ ___________ can be made using 5 cent and 7 cent stamps. (You should fill in the blank with the smallest value that works.)
Use strong induction to prove that every natural number n ≥ 2 can be written as...
Use strong induction to prove that every natural number n ≥ 2 can be written as n = 2x + 3y, where x and y are integers greater than or equal to 0. Show the induction step and hypothesis along with any cases
Please note n's are superscripted. (a) Use mathematical induction to prove that 2n+1 + 3n+1 ≤...
Please note n's are superscripted. (a) Use mathematical induction to prove that 2n+1 + 3n+1 ≤ 2 · 4n for all integers n ≥ 3. (b) Let f(n) = 2n+1 + 3n+1 and g(n) = 4n. Using the inequality from part (a) prove that f(n) = O(g(n)). You need to give a rigorous proof derived directly from the definition of O-notation, without using any theorems from class. (First, give a complete statement of the definition. Next, show how f(n) =...
Let a0 = 1, a1 = 2, a2 = 4, and an = an-1 + an-3...
Let a0 = 1, a1 = 2, a2 = 4, and an = an-1 + an-3 for n>= 3. Let P(n) denote an an <= 2^n. Prove that P(n) for n>= 0 using strong induction: (a) (1 point) Show that P(0), P(1), and P(2) are true, which completes the base case. (b) Inductive Step: i. (1 point) What is your inductive hypothesis? ii. (1 point) What are you trying to prove? iii. (2 points) Complete the proof:
Let a0 = 1, a1 = 2, a2 = 4, and an = an-1 + an-3...
Let a0 = 1, a1 = 2, a2 = 4, and an = an-1 + an-3 for n>= 3. Let P(n) denote an an <= 2^n. Prove that P(n) for n>= 0 using strong induction: (a) (1 point) Show that P(0), P(1), and P(2) are true, which completes the base case. (b) Inductive Step: i. (1 point) What is your inductive hypothesis? ii. (1 point) What are you trying to prove? iii. (2 points) Complete the proof:
Prove the following statement by mathematical induction. For every integer n ≥ 0, 2n <(n +...
Prove the following statement by mathematical induction. For every integer n ≥ 0, 2n <(n + 2)! Proof (by mathematical induction): Let P(n) be the inequality 2n < (n + 2)!. We will show that P(n) is true for every integer n ≥ 0. Show that P(0) is true: Before simplifying, the left-hand side of P(0) is _______ and the right-hand side is ______ . The fact that the statement is true can be deduced from that fact that 20...
1. Give a direct proof that the product of two odd integers is odd. 2. Give...
1. Give a direct proof that the product of two odd integers is odd. 2. Give an indirect proof that if 2n 3 + 3n + 4 is odd, then n is odd. 3. Give a proof by contradiction that if 2n 3 + 3n + 4 is odd, then n is odd. Hint: Your proofs for problems 2 and 3 should be different even though your proving the same theorem. 4. Give a counter example to the proposition: Every...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT