Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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. –  Arturo Magidin Oct 14 '11 at 16:15
    
Are $k$ and $l$ natural numbers?And have you tried to see if this is true for $n=9$? –  smanoos Oct 14 '11 at 16:16
2  
@smanoos: Remember that "naturals" often include $0$. –  Arturo Magidin Oct 14 '11 at 16:18
1  
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. –  André Nicolas Oct 14 '11 at 16:23
3  
This is one case of the Frobenius coin problem. A discussion is at en.wikipedia.org/wiki/Coin_problem –  Ross Millikan Oct 14 '11 at 16:33
show 1 more comment

3 Answers

up vote 2 down vote accepted

HINT $\rm\quad n\ =\ 3\:\bigg(\!\!\dfrac{n-5\:k}{3}\!\bigg)\: +\ 5\:k\ \ $ for $\rm\ \ k\: = \ {-}n\:\ mod\:\ 3,\ \ k \in \{0,1,2\}$

NOTE $\ $ For the underlying geometric intuition see this post on the Frobenius problem.

Per request in the comments, here are some examples with further detail.

$\begin{eqnarray} \rm n =\ 8,\ \ \ k &=& -8&\equiv\ 1,\ &\ \ 8\ &=\ 3\ (\ 8&-&5\cdot 1)/3 + 5\cdot 1\ =\ 3\cdot 1 + 5\cdot 1 \\ \rm n =\ 9,\ \ \ k &=& -9&\equiv\ 0,&\ \ 9 &=\ 3\ (\ 9&-&5\cdot 0)/3 + 5\cdot 0\ =\ 3\cdot 3 + 5\cdot 0 \\ \rm n = 10,\ \ k &=& -10&\equiv\ 2,& 10 &=\ 3\ (10&-&5\cdot 2)/3 + 5\cdot 2\ =\ 3\cdot 0 + 5\cdot 2 \\ \end{eqnarray}$

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

share|improve this answer
    
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. –  Lissa Oct 14 '11 at 23:12
    
@Lissa I've added some examples in the answer. –  Bill Dubuque Oct 17 '11 at 4:19
add comment

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.

share|improve this answer
    
I think you mean $3(3)$ and not $3(2)$. –  smanoos Oct 14 '11 at 16:22
    
@smanoos: why, yes, I did! Thank you. (-: –  Arturo Magidin Oct 14 '11 at 16:23
    
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. –  Lissa Oct 14 '11 at 17:05
    
@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) –  Arturo Magidin Oct 14 '11 at 17:13
    
@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? –  Arturo Magidin Oct 14 '11 at 17:16
show 2 more comments

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.

share|improve this answer
    
More explicitly, see my answer, which unifies the cases. –  Bill Dubuque Oct 14 '11 at 17:22
3  
@Bill Dubuque: We have opposite tendencies. I use $100$ words when $50$ will do. –  André Nicolas Oct 14 '11 at 17:31
    
But "Words" describing separate cases often obscure the general structure exhibited by a universal formula. –  Bill Dubuque Oct 14 '11 at 17:39
    
@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? –  Lissa Oct 15 '11 at 11:15
    
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$. –  André Nicolas Oct 15 '11 at 13:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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