Thread: prove by induction

Prove that if n>=12 then n can be written as a sum of 4's and 5's

Originally Posted by Singular

Prove that if n>=12 then n can be written as a sum of 4's and 5's

See this thread for the general idea.

Though in this case you will be assing 4 4's and taking away 3 5's. Take
a bit of care to make sure that you have enough 5s to take 3 away.

So suppose you can make n as a sum of 4's and 5's, add 4 4's, then if there
are three or more 5's take 3 5's out, you now have a total of n+1.

If there are no 5's take 5 4's (at this point we have a minimum of 7 of them)and replace with 4 5's, So now the 3 5's can be removed leaving a total of
n+1.

RonL

Hello, Singular!

Prove that if n > 12, then n can be written as a sum of 4's and 5's

I haven't devised an inductive proof, but more of an intuitive one.


Suppose n is a multiple of 4: . n = 4a, for a > 3.
. . (Our number has at least three 4's.)

We can make n + 1 by adding a 5 and removing a 4.

We can make n + 2 by adding another 5 and removing another 4.

We can make n + 3 by adding another 5 and removing another 4.


The next number is n + 4, which is the next multiple of 4.
. . And we can repeat the procedure.


Therefore, we can construct any number n > 12.