For all non-negative integers $n$ such that $n ≥ 8$, there exist non-negative integers $a_n$ and $b_n$ such that $3a_n+5b_n = n$

Question

The solution to this question below is a bit confusing to me. If anyone would be kind enough to explain how the inductive claim works and why it is true for $3a_{n+1} + 5b_{n+1} = n+1$ This would help me a lot, thank you in advance.

[1]: https://i.stack.imgur.com/GpM4X.jpg

Answer 1

HINT:

• $A_{8}=\{3,5\}$
• $A_{9}=\{3,3,3\}$
• $A_{10}=\{5,5\}$
• $A_{n}=A_{n-3}\cup\{3\}$

Answer 2

Claim : For every natural number $n\ge 8$, there exist nonnegative integers $a$ and $b$ with $3a+5b=n$

Base case $n=8$ : Take $a=1$ and $b=1$

Suppose, we have $3a+5b=n$

For $b\ge 1$, we have $3(a+2)+5(b-1)=3a+5b+1=n+1$

For $a\ge 3$, we have $3(a-3)+5(b+2)=3a+5b+1=n+1$

So, the induction step works whenever $b\ge 1$ or $a\ge 3$. The remaining case is $a<3$ and $b=0$, but the corresponding numbers are $0,3,6$, which are smaller than $8$