2

I have come up with:

Assume for any $n\ge 64$ there exists numbers $x$ and $y$ such that $n = 17x + 5y$

and also then that $n+1 = 17x + 5y + 1$

but am fairly new to the concept of induction and not sure where to go after this.

Derpm
  • 69
  • 2
    $$n+1=17x+5y+(5\cdot7-2\cdot17)=17(x-2)+5(y+7)$$ – lab bhattacharjee Oct 10 '17 at 05:59
  • I'm not clear on how you have reached this equation – Derpm Oct 10 '17 at 06:07
  • @Derpm (57 - 217) = 1, he knows that $5$ and $17$ are both relatively prime (in fact prime), so there exists a linear combination that adds to 1. – IntegrateThis Oct 10 '17 at 06:17
  • I see that now, my initial n+1 equation was wrong. – Derpm Oct 10 '17 at 06:23
  • @labbhattacharjee $x,y$ must be nonnegative integers, because you can't put a negative number of stamps on a letter. So your solution fails when $x=0$ or $x=1.$ (If $x$ and $y$ can be arbitrary integers, there is no need for the hypothesis $n\ge64.$) – bof Oct 10 '17 at 07:52
  • $n$ needs to be $\ge 64$ so how can a solution be reached with non-negative integers? – Derpm Oct 10 '17 at 08:13
  • $$64=17\cdot2+5\cdot6,65=17\cdot0+5\cdot13,66=17\cdot3+5\cdot3,67=17\cdot1+5\cdot10,68=17\cdot4+5\cdot0$$ $$69=17\cdot2+5\cdot7,70=17\cdot0+5\cdot14,71=17\cdot3+5\cdot4,72=17\cdot1+5\cdot11,73=17\cdot4+5\cdot1$$ – bof Oct 10 '17 at 08:44
  • Yes I have found those, or well, 64-68 as base cases. I am unclear how to carry on with the inductive phase. – Derpm Oct 10 '17 at 09:43
  • Wait, the solution is determined first by what n is, so x and y couldn't be non negative right? – Derpm Oct 10 '17 at 10:22

4 Answers4

0

You can exhibit combinations of stamps for $64,65,66,67$ and $68$ cents as your base case, and then use the inductive step of adding a $5$ cent stamp for any greater amount.

The inductive phase addresses values of $69$ cents or more and can assume that the previous $5$ lesser values all have valid combinations of stamps.

More explicitly:

Base case:

  • $n=64$: $2\times$ $17$c stamps and $6\times$ $5$c stamps:
  • $n=65$: you can fill these in
  • $n=66$:
  • $n=67$:
  • $n=68$:

Inductive step: For any $k\ge 69$, assume that $n$ cents in the previous five values can be made by $a_n\times$ $17$c stamps and $b_n\times$ $5$c stamps.

Then for $k$ cent value set $a_k = a_{k-5}$ and $b_{k} = b_{k-5}+1$, giving:
$\begin{align} 17 a_k + 5 b_k &= 17a_{k-5} + 5(b_{k-5}+1)\\ &= 17a_{k-5} + 5b_{k-5} + 5\\ &= (k-5) + 5 = k\\ \end{align}$
as required

Joffan
  • 39,627
  • I'm not sure how to carry on with the inductive phase other than the way other solutions have shown – Derpm Oct 10 '17 at 09:42
  • Added a more explicit inductive step. – Joffan Oct 10 '17 at 13:48
  • 1
    This is the only correct solution that has been posted, the only one that doesn't miss the whole point. The downvote is incomprehensible. – bof Oct 12 '17 at 04:46
0
  1. Base step: Show that there are values of $x$ and $y$ that satisfy $17x+5y=64$.
  2. Inductive step: Assume that there exist $x$ and $y$ such that $17x+5y=n$. Use that assumption to show that there must exist $x'$ and $y'$ such that $17x'+5y'=n+1$.

Checking the base step is important and I will leave that to you. For the inductive step, using $17x+5y=n$ we can re-write $n+1=17x+5y+1$. Then, use the hint given by lab bhattacharjee.

Srikant
  • 335
  • Right so I understand and have reached $n+1 = 17(x-2) + 5(y+7)$ in my own working- is this the proof (if so, how?) or do I need to find something further? – Derpm Oct 10 '17 at 06:22
  • does it satisfy the question because it ends up being $17$cents x something and $5$cents x something which was what I needed to prove? – Derpm Oct 10 '17 at 06:29
  • This solution is invalid because the problem requires that $x$ and $y$ are nonnegative integers. – bof Oct 10 '17 at 07:35
  • Of course, if $x,y$ are only required to be integers, not necessarily nonnegative, there is no need for the hypothesis $n\ge64;$ every integer can be expressed in the form $17x+5y$ for some integers $x$ and $y.$ – bof Oct 10 '17 at 07:38
0

Base case: show that it works for n = 64

17x + 5y = 64

$x = 2, y = 6$ [OK]

Inductive Step: supposing it works for $n$, prove it works for $n+1$

there must exist $x'$ and $y'$ such that:

$17x' + 5y' = n + 1$

using the hypothesis, we can say $n = 17x + 5y$

$17x' + 5y' = 17x + 5y + 1$

$17(x' - x) + 5(y' - y) = 1$

say $(x' - x) = a$ and $(y' - y) = b$

if there are $a$ and $b$ such that $17a + 5b = 1$, than there will exist satisfying $x'$ and $y'$.

$a = -2, \;b = 7 \implies 17(-2) + 5(7) = -34+35=1$

Then, as we know $x$ and $y$ exists by hypothesis, for $n+1$ you just need to use $x' = x - 2$ and $y' = y + 7$ and you will get it.

Daniel
  • 732
  • $x$ and $y$ are required to be nonnegative. – bof Oct 10 '17 at 07:35
  • How can the solution be reached then, where $x$ and $y$ are non-negative? – Derpm Oct 10 '17 at 08:11
  • @Derpm See the correct solution by Joffan. – bof Oct 10 '17 at 08:46
  • I think this is still correct. From what I know about induction it is an implication sort of situation, where if $n \ge 64$, then $n = 17x + 5y$ etc – Derpm Oct 10 '17 at 12:50
  • From the induction hypothesis, even if $x,y$ are nonnegative, we can't be sure that $x'=x-2$ is nonnegative. And it's clear that the question is asking for nonnegative numbers. (1) Can't put negative number of stamps on a letter. (2) The assumption $n\ge64$ is irrelevant if arbitrary integers are permitted, but it's just what we need to get $x,y\ge0$, since $17x+5y=63$ has no solution in nonnegative integers. – bof Oct 12 '17 at 04:43
0

You can exhibit combinations of stamps for $64,65,66,67,..., 99$ cents as your base case, for instance, and then use the inductive step.

More explicitly:

Base case:

  • $n=64$: $2\times$ $17$c stamps and $6\times$ $5$c stamps:
  • $n=65$: you can fill these in (with the help of a computer)
  • $n=66$:
  • $n=67$:
  • $\vdots$
  • $n=99$:

Inductive step: For any $99\leq k\leq n$, assume that $$k=17a_k+5b_k,$$ to some nonnegative integers $a_k$ and $b_k$.

Hence, $$n+1=17a_n+5b_n+1=17a_n+5b_n+(35-34)=17(a_n-2)+5(b_n+7).$$

If $a_n\geq 2$ the proof finishes.

Otherwise, note that $64\leq k=n+1-17\leq n$ and $k=17a_k+5b_k$.

It follows that $$n+1=17(a_k+1)+5b_k,$$ for instance.

José Claudinei Ferreira
  • 150