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

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


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






Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.