induction (1 Viewer)

[...]

Prove that, given enough 4cents and 7cents stamps, you can make any amount of postage 18cents or greater

hmm

i took the tradition approach (prove the base case its true, assume n is true and then prove n+1 is true)
but it didn't work out for one of the later cases

 

[shafqat]

Prove that, given enough 4cents and 7cents stamps, you can make any amount of postage 18cents or greater

hmm

i took the tradition approach (prove the base case its true, assume n is true and then prove n+1 is true)
but it didn't work out for one of the later cases

Do you mean 18 cents and any multiple of 18 cents?

 

[acmilan]

It means any number > 18 can be made solely of a number of 4 and 7 cents stamps. Ie 18, 19, 20, 21 ...

 

[withoutaface]

We can make 18 = 4+7+7
19 = 4+4+4+7
20 = 4+4+4+4+4
21 = 7+7+7

And for any higher we can just add 4n to any of these base cases, where n is any positive integer.

 

[shafqat]

Very nice and elegant. Why is it induction? I guess if you really want to prove it that way, write X = 4n + 7m. Then X + 1 = 4n + 7m + 1 and peel off 4s and 7s, eg 4(1 + p) etc. and then factorise.