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