1. ## Induction

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.

2. ## Re: Induction

not true for $n=15$

should be true for $n>15$

are we required to use induction?

3. ## Re: Induction

Originally Posted by Idea
not true for $n=15$

should be true for $n>15$

are we required to use induction?
The OP is true on non-negative integers, $\mathbb{Z}\setminus\mathbb{Z}^-$

4. ## Re: Induction

if we include $0$ in $\mathbb{Z}_+$ then it is true for $n>7$

otherwise it is true for $n>15$

5. ## Re: Induction

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?

6. ## Re: Induction

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?

7. ## Re: Induction

Originally Posted by VonNemo19
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 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.

8. ## Re: Induction

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.