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.)

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)