Results 1 to 8 of 8
Like Tree6Thanks
  • 1 Post By Idea
  • 1 Post By Plato
  • 1 Post By Idea
  • 1 Post By chiro
  • 1 Post By HallsofIvy
  • 1 Post By greg1313

Thread: Induction

  1. #1
    No one in Particular VonNemo19's Avatar
    Joined
    Apr 2009
    From
    Detroit, MI
    Posts
    1,848

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    668
    Thanks
    304

    Re: Induction

    not true for n=15

    should be true for n>15

    are we required to use induction?
    Thanks from VonNemo19
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,021
    Thanks
    2554
    Awards
    1

    Re: Induction

    Quote Originally Posted by Idea View Post
    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}^-
    Thanks from VonNemo19
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    668
    Thanks
    304

    Re: Induction

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

    otherwise it is true for n>15
    Thanks from VonNemo19
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    6,536
    Thanks
    1701

    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?
    Thanks from VonNemo19
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Apr 2005
    Posts
    18,958
    Thanks
    2740

    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?
    Thanks from VonNemo19
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Dec 2016
    From
    Earth
    Posts
    95
    Thanks
    46

    Re: Induction

    Quote Originally Posted by VonNemo19 View Post
    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.
    Last edited by greg1313; Mar 10th 2017 at 11:54 AM.
    Thanks from VonNemo19
    Follow Math Help Forum on Facebook and Google+

  8. #8
    No one in Particular VonNemo19's Avatar
    Joined
    Apr 2009
    From
    Detroit, MI
    Posts
    1,848

    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.
    Last edited by VonNemo19; Mar 10th 2017 at 04:05 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: Apr 21st 2011, 12:36 AM
  2. Replies: 10
    Last Post: Jun 29th 2010, 12:10 PM
  3. need help with Induction
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: Jan 18th 2010, 11:39 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 8th 2009, 09:33 PM
  5. Induction
    Posted in the Algebra Forum
    Replies: 5
    Last Post: Apr 18th 2008, 01:27 PM

/mathhelpforum @mathhelpforum