I'm trying to prove that for $n>13$ , there exists $x, y \in{Z_+}$ such that $n=3x+5y$. I'm having trouble with the extended inductive step. I would appreciate it if you don't just outright solve this for me. But if you do, use spoilers.
Hey VonNemo19.
I'd try and show that for certain numbers n = 2z and n = 2z + 1 that you can find integer solutions to that expression (i.e. look at different cases of numbers by divisibility and show they hold in all cases).
If you can't do odd and even then try looking at enough prime numbers for some period and use the inductive step on that.
Could you show us the attempts you make?
I would not use "induction" at all but rather use "Euclid's algorithm". Start from the obvious fact that 3(2)+ 5(-1)= 1 and multiply each side by n: 3(2n)+ 5(-n)= n. So, for every n, one solution is x= 2n, y= -n. But then it is clear that x= 2n- 5k, y= -n+ 3k is also a solution for any integer, k: 3(2n- 5k)+ 5(-n+ 3k)= 6n- 15k- 5n+ 15k= n.
Requiring that the solutions be positive means that we must have 2n- 5k> 0 and -n+ 3k> 0. That is, 3k> n and 5k< 2n. That is equivalent to n/3< k< 2n/5. For what values of n is there at least one integer between n/3 and 2n/5?
(I went ahead and gave my full attempt, because 1) it's the next day, and 2) I didn't see around giving hints.)
Starting with n = 16, inclusive, you can show that n = 3x + 5y, for positive integers x and y.
Case where y = 1, x > 3
- - - - - - - - - - - - - - - -
Base case
x = 4, y = 1
n = 3(4) + 5(1)
n = 12 + 5
n = 17
n + 1 =
3(4) + 5(1) + 1 =
3(1 + 3) + 5(3 - 2) + 1 =
3(1) + 3(3) + 5(3) - 5(2) + 1 =
3(1) + 5(3) + 9 - 10 + 1 =
3(1) + 5(3) =
3 + 15 =
18
Inductive step
Recall that y = 1.
n = 3x + 5(1)
n = 3x + 5
n + 1 = 3x + 5 + 1
n + 1 = 3x + 5 + (-9 + 10)
n + 1 = 3x - 9 + 5 + 10
n + 1 = 3(x - 3) + 5(1 + 2)
n + 1 = 3(x - 3) + 5(3)
Case where y > 1
- - - - - - - - - - - -
Base case
x = 2, y = 2
n = 3(2) + 5(2)
n = 6 + 10
n = 16
n + 1 =
3(2) + 5(2) + 1 =
3(4 - 2) + 5(1 + 1) + 1 =
3(4) - 3(2) + 5(1) + 5(1) + 1 =
3(4) + 5(1) - 3(2) + 5(1) + 1 =
3(4) + 5(1) - 6 + 5 + 1 =
3(4) + 5(1) =
12 + 5 =
17
Inductive step
n = 3x + 5y
n + 1 = 3x + 5y + 1
n + 1 = 3x + 5y + (6 - 5)
n + 1 = 3x + 6 + 5y - 5
n + 1 = 3(x + 2) + 5(y - 1)
Thus, by the Principle of Mathematical Induction, I have shown that the proposition, as I have restated it, is true.
Hey. Sorry about the absence. Yeah. We're talking about non negative solutions. I've made some progress. If I assume k, then I can always add 1 to both sides and then sub back for k, right? So, $k =3x_0+5y_0\rightarrow{}k +1=6+k-5=3(x_0+2)+5(y_0-1)$. But then $y -1\geq{0}$. So I get confused.