Can you please help me and tell, how should I move on? Can this be proved by induction?

Every natural number $n\geq 8$ can be represented as $n=3k + 5\ell$.

Thank you in advance

  • $\begingroup$ Welcome to math.SE. Please note that [linear algebra] is a particular discipline that deals with vectors, vector spaces, linear transformations, and matrices; it is an inappropriate tag for both questions you have asked so far. $\endgroup$ – Arturo Magidin Oct 14 '11 at 16:15
  • $\begingroup$ Are $k$ and $l$ natural numbers?And have you tried to see if this is true for $n=9$? $\endgroup$ – smanoos Oct 14 '11 at 16:16
  • 2
    $\begingroup$ @smanoos: Remember that "naturals" often include $0$. $\endgroup$ – Arturo Magidin Oct 14 '11 at 16:18
  • 1
    $\begingroup$ We need to be slightly more specific. The assertion should be that every natural number $n \ge 8$ can be represented as $n=3k+5l$, where $k$ and $l$ are non-negative integers. Check for $8$, $9$, $10$. Now is it clear? Yes, we can use induction, but you can do it without mentioning induction explicitly. $\endgroup$ – André Nicolas Oct 14 '11 at 16:23
  • 3
    $\begingroup$ This is one case of the Frobenius coin problem. A discussion is at en.wikipedia.org/wiki/Coin_problem $\endgroup$ – Ross Millikan Oct 14 '11 at 16:33

Hint $ $ If $\rm\,n\,$ is representable so too is $\rm\,n\!+\!\color{#c00}3$ (by adding $1$ to $\rm k)$ so if the $\,\color{#c00} 3\,$ consecutive integers $\,8,9,10\,$ are representable then induction $\Rightarrow$ so too are all larger integers $\,3\!+\![8,9,10],\,$ $\, 6\!+\![8,9,10]\,\ldots$

Remark $ $ The same idea works for any number of integers (or "coins", "stamps", "McNuggets", etc). For some underlying geometric intuition see this post on this so-called Frobenius problem (which includes a list of many of its related names to aid in literature searches).

Explicitly: $\rm\quad n\ =\ 3\bigg[\dfrac{n-5\:k}{3}\bigg] + 5\:k\ \ $ for $\rm\ \ k\: = \ {-}n\:\ mod\:\ 3,\ \ k \in \{0,1,2\}$

Thus $\rm\ \ 3\:m + \ \ 8\ =\ 3\:m + 3\cdot 1 + 5\cdot 1\ =\ 3\:(m+1) + 5\cdot 1$
and $\rm\ \ \ \ 3\:m + \ \ 9\ =\ 3\:m + 3\cdot 3 + 5\cdot 0\ =\ 3\:(m+3) + 5\cdot 0$
and $\rm\ \ \ \ 3\:m + 10\ =\ 3\:m + 3\cdot 0 + 5\cdot 2\ =\ 3\:(m+0) + 5\cdot 2$

yields the desired representations for all integers $\ge 8.$

  • $\begingroup$ Thank you for the response! I'm really beginner in "real" math,that's why I have to ask you some more questions. Could you please explain, what does the last part mean: k∈{0,1,2}, k≡−n(mod3). I've just read about congruence relation in wikipedia, but didn't understand, why -8 and 7 are congruent mod 5 (-8/5 rest -3; 7/5 rest 2 O_o). And in your hint k and -n are congruent mod 3. Could you please give me some more explanation. $\endgroup$ – Lissa Oct 14 '11 at 23:12
  • $\begingroup$ @Lissa I've added some examples in the answer. $\endgroup$ – Bill Dubuque Oct 17 '11 at 4:19

Clearly, $8$ can be represented as $3k+5\ell$, by taking $k=1$ and $\ell=1$.

Likewise, $9=3(3) + 5(0)$; and $10=3(0) + 5(2)$. So we can represent $8$, $9$, and $10$.

Now, assume that for $m\gt 10$, and you can represent all numbers strictly smaller than $m$ that are $8$ or larger (the induction hypothesis). To show that you can represent $m$, consider $m-3$ first.

  • $\begingroup$ I think you mean $3(3)$ and not $3(2)$. $\endgroup$ – smanoos Oct 14 '11 at 16:22
  • $\begingroup$ @smanoos: why, yes, I did! Thank you. (-: $\endgroup$ – Arturo Magidin Oct 14 '11 at 16:23
  • $\begingroup$ Thank you for response! I have some questions. By k>10 you mean some n'>10? What do you mean "To show that you can represent k, consider k−3 first"? IS looks like: n'+1 = 3k+5l, but I cannot move from this point. $\endgroup$ – Lissa Oct 14 '11 at 17:05
  • $\begingroup$ @Lissa: What you call the number on which you are doing induction does not matter. I like to call it "$k$"; if you want to call it "$n'$", I don't think the number is likely to object. Note that I am not doing regular induction ("assume it's true for $k$, show it is true for $k+1$"), I am using so-called strong induction ("assume it is true for every number strictly smaller than $k$, show it is true for $k$").(cont) $\endgroup$ – Arturo Magidin Oct 14 '11 at 17:13
  • $\begingroup$ @Lissa: (cont) See here, and here. The induction hypothesis, which I stated explicitly, is that every number less than $k$ (and greater than or equal to $8$) can be represented. We need to prove that $k$ can be represented. Now, if $k\gt 10$, then $k-3$ is a number that is smaller than $k$; and greater than or equal to $8$. So our induction hypothesis says that we can represent $k+3$. Go from there? $\endgroup$ – Arturo Magidin Oct 14 '11 at 17:16

We can avoid an explicit appeal to induction by using the fact that every natural number $n$ has remainder $0$, $1$, or $2$ on division by $3$. Let $n \ge 8$.

If $n$ has remainder $2$ on division by $3$, then $n-8$ is divisible by $3$, say $n-8=3m$. Represent $8$ using $8=3\cdot 1+5\cdot 1$. Then add $m$ $3$'s.

If $n$ has remainder $0$ on division by $3$, then $n-9$ is divisible by $3$, say $n-9=3m$. Represent $9$ using $9=3\cdot 3 +5\cdot 0$. Then add $m$ $3$'s.

If $n$ has remainder $1$ on division by $3$, then $n-10$ is divisible by $3$, say $n-10=3m$. Represent $10$ using $10=3\cdot 0 +5\cdot 2$. Then add $m$ $3$'s.

The argument for remainder $0$ was a little silly, since if $n$ has remainder $0$ on division by $3$, we can clearly use a bunch of $3$'s to represent $n$. But we wanted the solutions for the three cases to use a single template.

  • $\begingroup$ More explicitly, see my answer, which unifies the cases. $\endgroup$ – Bill Dubuque Oct 14 '11 at 17:22
  • 3
    $\begingroup$ @Bill Dubuque: We have opposite tendencies. I use $100$ words when $50$ will do. $\endgroup$ – André Nicolas Oct 14 '11 at 17:31
  • $\begingroup$ But "Words" describing separate cases often obscure the general structure exhibited by a universal formula. $\endgroup$ – Bill Dubuque Oct 14 '11 at 17:39
  • $\begingroup$ @André Nicolas, thank you for detailed answer - exactly the way, I need :) Please, can you tell, what are we doing here in general words? The principle? $\endgroup$ – Lissa Oct 15 '11 at 11:15
  • $\begingroup$ We are finding non-negative solutions of linear diophantine equations. In general, if $a$ and $b$ are relatively prime positive integers, for any $n > ab-a-b$ there are non-negative integers $x$, $y$ such that $ax+by=n$. $\endgroup$ – André Nicolas Oct 15 '11 at 13:51

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.