Ask Question
30 August, 18:53

Show that any integer n > 12 can be written as a sum 4r + 5s for some nonnegative integers r, s. (This problem is sometimes called a postage stamp problem. It says that any postage greater than 11 cents can be formed using 4 cent and 5 cent stamps.)

+3
Answers (1)
  1. 30 August, 20:49
    0
    Use induction for the prove

    Step-by-step explanation:

    Mathemathical induction is an useful method to prove things over natural numbers, you check for the first case, supose for the n and prove using your hypothesis for n+1

    there says any integer bigger than 12 can be written as 4r+5s

    so first number n can be is 13.

    we can check n=13 = 4*2+5*1 r=2 and s=1 give 13.

    Now we suppose n can be written as 4r+5s

    and we can check if n+1=4r'+5s' with r' and s' integers.

    we replace n as 4r+5s because that is our hypotesis

    n+1=4r+5s+1

    if we write that 1 as 5-4

    4r+5s+1

    4r+5s+5-4

    then we can write

    4 (r-1) + 5 (s+1), we got n+1 = 4 (r-1) + 5 (s+1) where r-1 and s+1 are non negative integers. because r and s were no negative integers (if r is not 0)

    what if r=0?

    if r is 0, n is a multiple of 5 and n+1 can be written as 5s+1

    first multiple of 5 we can write is 15 since n is bigger than 12, then smaller s is 3.

    for any n+1 we can write

    n+1=5s+1=5 (s-3) + 3*5+1=5 (s-3) + 4*4, s-3 is 0 or bigger.

    (check 3*5+1 is 16, the same as 4*4)
Know the Answer?
Not Sure About the Answer?
Find an answer to your question ✅ “Show that any integer n > 12 can be written as a sum 4r + 5s for some nonnegative integers r, s. (This problem is sometimes called a ...” in 📘 Mathematics if you're in doubt about the correctness of the answers or there's no answer, then try to use the smart search and find answers to the similar questions.
Search for Other Answers