0
$\begingroup$

Prove an greater than 11 can be written as a sum of only 3's and only 7's.

Is there a way to do this by strong induction. I would greatly appreciate someone showing me how to apply the classic strong induction technique to this question.

$\endgroup$
2
  • $\begingroup$ Hint: You only need to worry about the case when $k=2 \mod 3$. Can you find out why? $\endgroup$
    – user801306
    Commented Feb 5, 2021 at 0:31
  • $\begingroup$ The general problem is called the Frobenius coin problem, the resolution to which is called Sylvester's theorem or the Chicken McNugget theorem. $\endgroup$
    – Favst
    Commented Feb 5, 2021 at 0:32

1 Answer 1

Reset to default
0
$\begingroup$

$$12=3+3+3+3,13=3+3+7,14=7+7.$$

Now assume the result to be true for all $n$ such that $12\le n\le k$, where $k\ge14$. Then consider $n=k+1$.

$n=3+(k-2)$ where, by assumption $k-2$ can be expressed as an appropriate sum. Hence, by strong induction, every number greater than $12$ can be so expressed.

$\endgroup$
1
  • 1
    $\begingroup$ Yes - it's fine. It was a clever idea to use the "two or more" method. $\endgroup$
    – user502266
    Commented Feb 5, 2021 at 0:39

You must log in to answer this question.