Prove that for all n>11 we can represent $n$ by $n=3a+7b$

Question

So i decided to do this using normal induction.

$P(12)$ true since $12=4 \times 3$

$P(k)=3a+7b$

$P(k+1)=3(a-2)+7(b+1)$

So i think it is proven but i cannot see why we have to assume $n$ is larger than $11$. I mean i know it is impossible for $11$ but lets say $9$.

$P(9)$ true since $9=3 \times 3$

$P(k)=3a+7b$

$P(k+1)=3(a-2)+7(b+1)$.

I am surely missing something but i don't know what ;/

Answer 1

Following your induction concept,

Since we know $3a+7b >10$, we have $a\geq 2$ or $b\geq 2$. Otherwise $a\leq1$ and $b\leq1$ so the sum would be less than or equal to $10$.

(1) If $a\geq 2$ then let $P(k+1)=3(a-2)+7(b+1)$ where $a-2\geq 0$.

(2) If $b\geq 2$ then let $P(k+1)=3(a+5)+7(b-2)$ where $b-2\geq 0$

Answer 2

Provided $a$ and $b$ are non-negative integers, we can write

$$ 12 = 3 \times 4 + 7 \times 0 $$ $$ 13 = 3 \times 2 + 7 \times 1 $$ $$ 14 = 3 \times 0 + 7 \times 2 $$

and then for $n = 15$ and up, we can simply write $n - 3$ in the required form, and then increment $a$ by $1$.