Mathematical induction: Why is my proof wrong? What would be the correct way to approach this problem?

Question

The statement is: Prove that for every integer n greater than or equal to $8$, $n$ can be written as a sum of $3$’s and $5$’s.

1) Let $n=8$. Then $n=3(1)+(5)(1)$, and so n has been expressed as a sum of $3$’s and $5$’s.

2) Let $k\ge 8$ and suppose $k$ can be written as a sum of $3$’s and $5$’s. That means there is a solution to the equation $k=3r+5s$ where $r$, $s \geq 0$.

3) By the inductive assumption, $k + 1 = (3r+5s) + 1$.

4) Since $\gcd(3,5) = 1$ then when know that there exists an integer solution to the equation $3x+5y=1$. Then $k + 1 = (3r+5s) + 1 \rightarrow k + 1 = (3r+5s)+(3x+5y) = 3(r+x)+5(s+y)$, and $r+x$ and $s+y$ are integers since $r$, $s$, $x$, $y$ are all integers. Thus $k+1$ has been expressed as the sum of $3$'s and $5$'s and the statement had been proved.

Edit 1: Is my error related to the "All horses are the same color" paradox? https://en.wikipedia.org/wiki/All_horses_are_the_same_color

Answer 1

To prove the result, which I think intends to use non-negative numbers of 3's and 5's, you can use the base case, checking all numbers from 8 to 15, and then inductive step just subtracts 8 and adds 3+5...

---

UPDATE From Matt Samuel's hint below, checking 8,9,10 is enough since you can then subtract 3 in the inductive step...

Answer 2

$P(8) = 5 + 3$

Let's say $P(n)= \sum_{i=1}^K 3 + \sum_{i=1}^N 5 = 3 K + 5 N$ then

$P(n+1) = 3 K + 5 N + 1 = 3 K + 5 (N-1) + 5 + 1 = 3 (K+2) + 5 (N -1)$