54
$\begingroup$

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$.

I can't prove that but it's obvious. What do you think about this?

$\endgroup$
  • 1
    $\begingroup$ This seems to me a good formulation, even though it is not the usual one. (Maybe it is better!) It requires only the proofs of the last three statements, for which you can get a good hint by looking at how you change $m$ and $n$ in the sum $x=3m+5n$ when you transition from $x=a_1$ to $b_1$, from $b_1$ to $c_1$, and from $c_1$ to $a_2$. $\endgroup$ – David K Mar 8 '15 at 20:16
  • 4
    $\begingroup$ This is the well-known Frobenius Theorem/Chicken McNuggets Theorem/Coin problem/etc $\endgroup$ – smci Mar 9 '15 at 10:26
  • $\begingroup$ do you need to use induction? $\endgroup$ – rafforaffo Mar 9 '15 at 12:31

13 Answers 13

133
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ Very nice -- best proof in this thread, in my opinion. $\endgroup$ – sardoj Mar 8 '15 at 19:57
  • 4
    $\begingroup$ Very pretty, well done for using one base case only. $\endgroup$ – Joffan Mar 8 '15 at 20:30
  • 2
    $\begingroup$ It'd be really neat if there was an animation of this proof! $\endgroup$ – Casey Chu Mar 9 '15 at 6:12
  • 2
    $\begingroup$ You also need to prove that the sum representation of every number has at least three 3s or at least one 5 to ensure at least one of the cases always applies. This is not difficult. 8 is 3 + 5, case 1, which becomes 3 + 3 + 3 = 9. By case 2, 9 becomes 5 + 5 = 10. From then on, the cycle of replacing always removes one 5 and adds two 3s, removes one 5 and adds two 3s, then removes three 3s and adds two 5s. Thus, all n ≥ 8 congruent to 0 (mod 3) contain three or more 3s; all n ≥ 8 congruent to 1 (mod 3) contain two 5s; and all n ≥ 8 congruent to 2 (mod 3) contain one 5. $\endgroup$ – Clement Cherlin Mar 9 '15 at 8:03
  • 26
    $\begingroup$ @ClementCherlin You don't need any complicated argument to see that every number $\ge8$ with a sum representation has at least three $3$'s or one $5$. If both are false then it contains no $5$'s and at most two $3$'s; thus it is at most $6$. $\endgroup$ – Mario Carneiro Mar 9 '15 at 11:12
12
$\begingroup$

I would avoid induction and use the elementary Euclidean division algorithm (Eda).

Let $n\geq8$ be an integer. Then, by the Eda, there exist integer $q$ and $r$ such that $r\in\{0,1,2\}$ and $$n=3q+r.$$

  • If $r=0$, we are done since $n=3q$.

  • If $r=1$, then $q\geq3$ (because $n\geq8$). Hence $n=3(q-3)+10$.

  • If $r=2$, then $q\geq2$ (because $n\geq8$). Hence $n=3(q-1)+5$.

$\endgroup$
  • 3
    $\begingroup$ This is very nice and deserves more up-votes. The inductive proof that has 100+ votes is also nice, but there is something to be said for directness. $\endgroup$ – Silvio Levy Mar 16 '15 at 16:48
  • $\begingroup$ I upvoted this. To adress Silvio's comment ; I notice that the induction and this proof are very similar ... ironically an argument both ways imho : a reason to upvote this or a reason not to. $\endgroup$ – mick Dec 28 '17 at 21:34
11
$\begingroup$

Write $x=8n+k$ for $0\leq k<8$ and $n\geq 1$. Because $8n=(3+5)n$, the problem is clear if $k=0,3,5$. Let's consider the remaining 5 cases: \begin{align*} k=1 & \implies 8n+1=5(n-1)+3(n+2),\\ k=2 & \implies 8n+2=5(n+1)+3(n-1),\\ k=4 & \implies 8n+4=5(n-1)+3(n+3),\\ k=6 & \implies 8n+6=5n+3(n+2),\\ k=7 & \implies 8n+7=5(n+2)+3(n-1). \end{align*} Note that $k=4$ is based on $k=1$ (just add one more $3$) and, similarly, $k=6$ and $k=7$ follow from $k=1$ and $k=2$, respectively. So in fact, we have really only considered 2 cases.

$\endgroup$
10
$\begingroup$

You are almost done, actually you can prove it even without induction:

If $\forall x \ge 8$ and you must prove that $x \in \mathbb{N} \land x = 5a + 3b$

Let $x_1$ be 8 and consider your base cases:

$x_1 = 8 = 3 ⋅ 1 + 5 ⋅ 1$

$x_2 = 9 = 3⋅3 + 5 ⋅ 0$

$x_3 = 10 = 3⋅0 +5⋅2$

This is true for the first 3 $n$ (1, 2 and 3) of $x_n$.

Now, consider the following:

$x_4 = 11 = x_1 + 3$

$x_5 = 12 = x_2 + 3$

$x_6 = 13 = x_3 + 3$

$x_7 = 14 = x_4 + 3$

$x_8 = 15 = x_5 + 3$

$...$

$x_n = x_{n-3} + 3 \,\,\,\,\,\,\forall n \gt 3$

As you can see from the pattern, it's obvious that you are summing only multiples of 3 basing on your previous results (which were also sums of multiples of threes and multiples of fives).

And you may also note that as soon as you sum 5 threes ($3+3+3+3+3 = 15 = 3⋅5$) you can safely replace them with 3 fives ($5 + 5 + 5 = 15 = 3⋅5$)

The previous equation leads to a recurrence relation and you can say with certainty that your statement is true $\forall x \ge 8$

$\endgroup$
  • 1
    $\begingroup$ I upvoted this. I like the idea that you only focus on 3 ! $\endgroup$ – mick Dec 28 '17 at 21:36
7
$\begingroup$

This is some mixture of Bezout's Lemma and Frobenius coin problem. Frobenius coin problem claims that if $a_1$ and $a_2$ are coprime numbers then every number bigger or equal to $(a_1-1)(a_2-1)$ can be written in the form $a_1x + a_2y$ for some non-negative integers $x,y$.

Write $a_1=3$ and $a_2=5$ in you case and you've got the answer. Anyway a inductive proof wouldn't be much harder.

$\endgroup$
  • 3
    $\begingroup$ Of course, using the Frobenius coin problem / lemma doesn't avoid the inductive proof, it just hides it in the proof of the Frobenius coin lemma. $\endgroup$ – LSpice Mar 8 '15 at 22:31
  • 1
    $\begingroup$ The $(a_1-1)(a_2-1)$ result is due to J.J. Sylvester. $\endgroup$ – MJD Mar 9 '15 at 12:50
7
$\begingroup$

1.if the integer can be written as $3s$, then set $a=0$

2.if the integer can be written as $3s+1$, set $a=2$, $10+3b=3s+1$,b=s-3

3.if the integer can be written as $3s+2$, set $a=1$, $b=s-1$

I am sure you have got the idea.

$\endgroup$
3
$\begingroup$

Your base case work is fine.

For the induction, you can assume (1) $k\ge 10$ and (2) all cases from $n=8$ to $n=k$ hold.

Then it is simply a matter of noting that we have $k-2=5a+3b$ and so we can say that $k+1 = 5a+3(b+1)$ as required.

$\endgroup$
  • 1
    $\begingroup$ This is the best answer to the original question. $\endgroup$ – Cirdec Mar 9 '15 at 17:58
2
$\begingroup$

Really late to the party, but here is a very short and sweet approach:

Claim: For each integer $n\geq 8$, let $S(n)$ be the statement that $n$ is expressible as a sum of $3$'s and $5$'s.

Base step: Since $8=3+5, 9=3+3+3, 10=5+5, S(8), S(9)$, and $S(10)$ are true.

Inductive step ($S(k)\to S(k+3)$): Let $k\geq 8$ and assume that $S(k)$ is true, where for some non-negative integers, $a,b,k = a\cdot 3+b\cdot 5$. Then $$ k+3=(a+1)\cdot 3+b\cdot 5, $$ a sum of $3$'s and $5$'s, so $S(k+3)$ is true.

By mathematical induction, three cases of induction actually, for all $n\geq 8, S(n)$ is true. $\blacksquare$

$\endgroup$
0
$\begingroup$

Any number is of the form $5k+1$, $5k+2$, $5k+3$, $5k+4$ and $5k+5$.

If $n=5k+3$ then nothing to prove.

$n=5k+1 \implies n=5(k-1)+2\cdot3$

$n=5k+2 \implies n=5(k-2)+4\cdot3$

$n=5k+4\implies n=5(k-4)+8\cdot3$

$n=5k+5\implies n=5(k-2)+5\cdot 3$

Hence for all $k\ge5$ the result holds.

Hence for all $n\ge 25$ the result hold.

What is left is to check the remaining cases and that is also true.

Hence the proposition is true.

$\endgroup$
0
$\begingroup$

Let $P(m)$ be the proposition that $k$ can be represented by a sum of fives and threes for all $m-2 \le k \le m$. $P(10)$ is true, since $8=5+3$, $9=3+3+3$, and $10=5+5$. This is the base case. And if $P(m)$ is true, then so is $P(m+1)$, since (applying the inductive hypothesis at the *): $$m+1=(m-2)+3 =^*(3a+5b)+3=3(a+1)+5b.$$ By induction on $m$, then, $P(m)$ is true for all $m\ge 10$; hence $k$ can be represented by a sum of fives and threes for all $k \ge 8$.

$\endgroup$
0
$\begingroup$

Starting with 8, let's investigate the pattern. 5*1 + 3*1 = 8, 5*0 + 3*3 = 9, 5*2 + 3*0 = 10, you can keep writing this out for it to be easier to see. In general you can increase every number by 1 simply by increasing the previous integer by 6 increase the 3*2 and decreasing by 5 (5*1) hence increasing the integer by 1 (6-5). In the case that your previous value of 5 was 0 and you can't decrease, you will increase the 5 twice (5*2=10) and decrease the 3 3 times (3*3=9) the difference is 1. Hence, every number can be generated this way.

$\endgroup$
  • $\begingroup$ Welcome to MSE. Please edit and use MathJax to properly format math expressions. $\endgroup$ – Lee David Chung Lin Jul 27 '19 at 14:55
  • $\begingroup$ @LeeDavidChungLin sorry, I apologize. I need to learn how to use it. Is my proof correct? $\endgroup$ – mathlover Jul 27 '19 at 15:08
-1
$\begingroup$

Lets call $T$ every multiple of three: $T$ satisfies the condition. Numbers are $T, T-1,$ or $T-2$.

for $n > 3\cdot 2+1$:

$$n=T \implies n=3k $$ $$n=T-1 \implies n= 3\cdot 2 - 1 + 3(k-2) = 5 + 3(k-2)$$ $$n=T-2 \implies n= 3\cdot 4 - 2 + 3(k-4) = 10 + 3(k-2)$$

$\endgroup$
-1
$\begingroup$

I'm attempting to answer the question intuitively:

Every third number is a multiple of 3, and can definitely be written as a sum of 3s and 5s: $3x$ + $5$ x $0$.

Now we need to deal with numbers $y$ for which $y mod 3 = 1$ and $y mod 3 = 2$

For $y mod 3 = 2$: We know that $5 mod 3 = 2$, so 5 x 1 + 3$x$ should give us all numbers $y$ where $y mod 3 =2$ For $y mod 3 = 1$: We know that $5$ x $2 mod 3 = 1$, so 5 x 2 + 3$x$ should give us all numbers $y$ where $y mod 3 =1$

The smallest case in which we can use this proof is 5 x 2 + 3 x 0 = 10

We can show it is possible for 8 and 9 as 5+3 =8 and 3 x 3 =9

Hence, we can show that is possible for all numbers greater than or equal to 8.

This is also proves that the maximum multiplier we would need for 5 is 2.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.