# Proof that every number ≥ 88 can be represented by a sum of fives and threes.

Can you check if my proof is right?

Theorem. $\forall x\geq8, x$ can be represented by $5a + 3b$ where $a,b \in \mathbb{N}$.

Base case(s): $x=8 = 3\cdot1 + 5\cdot1 \quad \checkmark\\ x=9 = 3\cdot3 + 5\cdot0 \quad \checkmark\\ x=10 = 3\cdot0 + 5\cdot2 \quad \checkmark$

Inductive step:

$n \in \mathbb{N}\\a_1 = 8, a_n = a_1 + (x-1)\cdot3\\ b_1 = 9, b_n = b_1 + (x-1)\cdot3 = a_1 +1 + (x-1) \cdot 3\\ c_1 = 10, c_n = c_1 + (x-1)\cdot3 = b_1 + 1 + (x-1) \cdot 3 = a_1 + 2 + (x-1) \cdot 3\\ \\ S = \{x\in\mathbb{N}: x \in a_{x} \lor x \in b_{x} \lor x \in c_{x}\}$

Basis stays true, because $8,9,10 \in S$

Lets assume that $x \in S$. That means $x \in a_{n} \lor x \in b_{n} \lor x \in c_{n}$.

If $x \in a_n$ then $x+1 \in b_x$,

If $x \in b_x$ then $x+1 \in c_x$,

If $x \in c_x$ then $x+1 \in a_x$.

Proof by induction.
For the base case $n=8$ we have $8=5+3$.
Suppose that the statement holds for $k$ where $k\gt 8$. We show that it holds for $k+1$.

There are two cases.

1) $k$ has a $5$ as a summand in its representation.

2) $k$ has no $5$ as a summand in its representation.

For case 1, we delete “that $5$” in the sum representation of $k$ and replace it by two “$3$“s ! This proves the statement for $k+1$.

For case 2, since $k\gt 8$, then $k$ has at least three “$3$“s in its sum representation. We remove these three $3$‘s and replace them by two fives! We obtain a sum representation for $k+1$. This completes the proof.