# Prove that each integer n ≥ 12 is a sum of 4's and 5's using strong induction

So I've been given the following problem: Prove that each integer n ≥ 12 is a sum of 4's and 5's What I have so far: (Basis):

n ≥ 12 Therefore,

12 ≤ 4(x) + 5(y)

x = 3 | y = 0

12 ≤ 4(3) + 5(0)

12 ≤ 12 = Correct

However, what I don't understand is how would I use the x & y variable in induction step. Where exactly would I place these? and how would I go on to solve this?

The trick to these sorts of problems is to realize that if we can find four consecutive integers ($$4$$ is the smallest of our numbers we're taking a combination of) that can be represented as a non-negative sum of the fours and fives.

For example $$12 = 4(3) + 5(0)$$

$$13 = 4(2) + 5(1)$$ $$14 = 4(1)+ 5(2)$$ $$15 = 4(0) + 5(3).$$

With this information is it clear how you could represent 16? Just take the solution from the 12 case, and add 4! (so increase $$x$$ by $$1$$.)

Here's the formal argument. Let $$P(n)$$ be the open sentence "$$n$$ can be written as a non-negative combination of $$4$$ and $$5$$". By what we've shown above, we know that $$P(k)$$ is true for $$k = 12,13,14,15.$$ We wish to prove that $$P(k+1)$$ is true. Our strong inductive hypothesis is to suppose that for some $$k \in \mathbb{Z}$$ that for every $$i$$ with $$12\leq i\leq k$$ that $$P(k)$$ is true, and we need to prove that $$P(k+1)$$ is true.

If $$k = 12,13$$ or $$14$$, we've already seen that $$p(k+1)$$ is also true, so suppose that $$k \geq 15$$. Then we know that $$12 \leq k-3\leq k$$ so then by our strong inductive hypothesis, there exists $$x,y \in \mathbb{Z}$$ such that $$k-3 = 4(x) + 5(y)$$. Then adding $$4$$ to both sides gives that $$k+1 = 4(x+1)+5(y)$$ so that $$P(k+1)$$ is true. Thus by the principle of mathematical induction, $$P(n)$$ must be true for all $$n \geq 12$$.

• Wow this is very detailed and helped me understand it more, thank you! – MathNoob Feb 15 '19 at 4:15
• No problem! I'm glad this helped! – JonHales Feb 15 '19 at 4:17

$$4x+5y=\underbrace{4(x-1)+5y}_{n-4}+4$$

So, if $$n-4$$ is expessible so will be $$n$$

$$12=4\cdot3$$

$$13=2\cdot4+5$$

$$14=4+2\cdot5$$

$$15=3\cdot5$$