Results 1 to 9 of 9

Math Help - Prove by mathematical induction

  1. #1
    Member
    Joined
    Oct 2010
    Posts
    95

    Prove by mathematical induction

    Prove by induction or strong induction that every even integer n greater than 30 can be written in the form: n=6x+10y, \; \; where \; x,y \in \mathbb{Z}^{+}

    So I started off with my basis step this way:
    Basis \;  Step: \; n=16
    2n=6x+10y
    2(16)=6\cdot2 + 10\cdot 2
    32=6\cdot2 + 10\cdot 2
    So the basis step is true.

    Then follows the inductive step:
    Inductive \; Step: \; Assume \; 2(k+1)=6x+10y \;is \; true \; for \; k=n
    2k+2=6x+10y

    Then I realise I am stuck here. I don't know how I should move on from here. The usual inductions are like I could find something that looks like the basis step and then replace the k+1 part with the basis claim. But I can't do this in this one.

    Thanks for any help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member TheChaz's Avatar
    Joined
    Nov 2010
    From
    Northwest Arkansas
    Posts
    600
    Thanks
    2
    Quote Originally Posted by xEnOn View Post
    Prove by induction or strong induction that every even integer n greater than 30 can be written in the form: n=6x+10y, \; \; where \; x,y \in \mathbb{Z}^{+}

    So I started off with my basis step this way:
    Basis \;  Step: \; n=16
    2n=6x+10y
    2(16)=6\cdot2 + 10\cdot 2
    32=6\cdot2 + 10\cdot 2
    So the basis step is true.

    Then follows the inductive step:
    Inductive \; Step: \; Assume \; 2(k+1)=6x+10y \;is \; true \; for \; k=n
    2k+2=6x+10y

    Then I realise I am stuck here. I don't know how I should move on from here. The usual inductions are like I could find something that looks like the basis step and then replace the k+1 part with the basis claim. But I can't do this in this one.

    Thanks for any help.
    Why is your basis step n = 16 ???
    It states that n must be greater than 30.

    Oh... I somewhat see where you're going. I think strong induction is in order.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2010
    Posts
    95
    Actually, before this, I had my n=32. But I got stuck as soon as I started my basis step because I don't know how I can get even number from n=32. Making it n+2 does work all the time if n happens to be an odd number then adding 2 will still make it an odd number.

    So I tried the other way to have it as 2n instead. But I still get stuck.

    Oh... I somewhat see where you're going. I think strong induction is in order.
    Why is strong induction better? I feel like I get stuck too because I need to keep finding the correct x and y for all the different values of even integer n to make sure the P(16) and P(17)...P(n) are all true. And I don't know at which P(##) I can stop to be considered proved.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,854
    Thanks
    321
    Awards
    1
    Quote Originally Posted by xEnOn View Post
    Prove by induction or strong induction that every even integer n greater than 30 can be written in the form: n=6x+10y, \; \; where \; x,y \in \mathbb{Z}^{+}

    So I started off with my basis step this way:
    Basis \;  Step: \; n=16
    2n=6x+10y
    2(16)=6\cdot2 + 10\cdot 2
    32=6\cdot2 + 10\cdot 2
    So the basis step is true.

    Then follows the inductive step:
    Inductive \; Step: \; Assume \; 2(k+1)=6x+10y \;is \; true \; for \; k=n
    2k+2=6x+10y

    Then I realise I am stuck here. I don't know how I should move on from here. The usual inductions are like I could find something that looks like the basis step and then replace the k+1 part with the basis claim. But I can't do this in this one.

    Thanks for any help.
    How about this. I'll work with your idea of replacing n with 2n. You have the base case so let there be a value of n, k, such that the theorem holds. We need to show that the theorem holds for k + 1.

    What does it mean for the theorem to hold? Well we need to prove that x', y' in Z+ exist. So let's start with

    2k = 6x + 10y

    We want to find x' and y' such that
    2(k + 1) = 6x' + 10y'

    2k + 2 = 6x' + 10y'

    (6x + 10y) + 2 = 6x' + 10y' <--Using the hypothesis step

    2 = 6(x' - x) + 10(y' - y)

    We need to show that there exist x' and y' such that the above equation holds and x' and y' are integers. I'll leave this step to you.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2010
    Posts
    95
    I went on and did this:


    Does this consider proven? I found it a little weird. I used the x=2 and y=2 which I found in the basis step in this and it turns out that n=34. So n really did advance from 32 to 34 and 34 is also an even number. But does this tell anything and is it even correct?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,854
    Thanks
    321
    Awards
    1
    Quote Originally Posted by xEnOn View Post
    I went on and did this:


    Does this consider proven? I found it a little weird. I used the x=2 and y=2 which I found in the basis step in this and it turns out that n=34. So n really did advance from 32 to 34 and 34 is also an even number. But does this tell anything and is it even correct?
    Well, I was simply going to say that if we have x' - x = -3 and y' - y = 2 then 2 = 6(x' - x) + 10(y' - y). Thus x' - x = -3 is an integer and thus x' is an integer. Similar for y'. Thus integers x' and y' exist such that 2(k + 1) = 6x' + 10y' and the theorem is proved.

    As I was typing this I thought of a potential problem. x' and y' must be positive integers according to the problem statement. With x' - x = -3 we would have to show also that x' = x - 3 > 0 which means we need to prove that x > 3. Have to think about that one.

    -Dan

    Edit: Recall that you reset the problem so it was 2n = 6x + 10y. so your next to last step should be 2 = 2n - 32. However if you use this line of reasoning then all you've shown is that the theorem holds for 2n = 34. Not for all n.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Oct 2010
    Posts
    95
    ahh.. Thanks!
    So x' and y' can be another integer number so long as {x}'-x=-3 and {y}'-y=2 to consider the theorem proved, right?

    For the positive integer problem, can we say that we only consider the case when x'=4 and x=1, and y'=3 and y=1?
    So the equation will become 2=6(x' - 1) + 10(y' - 1) and both x' and y' must be positive integers now. But would this miss out any possible cases that also proves the theorem?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by xEnOn View Post
    Prove by induction or strong induction that every even integer n greater than 30 can be written in the form: n=6x+10y, \; \; where \; x,y \in \mathbb{Z}^{+}

    So I started off with my basis step this way:
    Basis \;  Step: \; n=16
    2n=6x+10y
    2(16)=6\cdot2 + 10\cdot 2
    32=6\cdot2 + 10\cdot 2
    So the basis step is true.

    Then follows the inductive step:
    Inductive \; Step: \; Assume \; 2(k+1)=6x+10y \;is \; true \; for \; k=n
    2k+2=6x+10y

    Then I realise I am stuck here. I don't know how I should move on from here. The usual inductions are like I could find something that looks like the basis step and then replace the k+1 part with the basis claim. But I can't do this in this one.

    Thanks for any help.
    You could also have proceeded thus...


    P(k)

    n=2k=2(3x+5y) is a positive integer


    P(k+1)

    m=2(k+1)=2(3x+5y+1) is also a positive integer.

    Show that P(k+1) will be true if P(k) is true


    Proof

    m=2(3x+5y)+2

    which is even if n is even.

    Test for the base case...
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,854
    Thanks
    321
    Awards
    1
    Quote Originally Posted by xEnOn View Post
    ahh.. Thanks!
    So x' and y' can be another integer number so long as {x}'-x=-3 and {y}'-y=2 to consider the theorem proved, right?

    For the positive integer problem, can we say that we only consider the case when x'=4 and x=1, and y'=3 and y=1?
    So the equation will become 2=6(x' - 1) + 10(y' - 1) and both x' and y' must be positive integers now. But would this miss out any possible cases that also proves the theorem?
    Well, x and y are set by 2k = 6x + 10y, so we can't adjust those. Good thought, though.

    Yeah, I was afraid something like this would happen. 36 = 6(1) + 10(3). So x does not have to be greater than 3. I'm not sure where, but there must be a flaw in my work. Sorry about that.

    -Dan

    Edit: Side thought. I wonder if x and y are unique? Hmmmm...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  2. Prove By Mathematical Induction
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: May 30th 2010, 10:22 AM
  3. using mathematical induction to prove something
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: April 30th 2008, 07:32 PM
  4. Prove by Mathematical Induction
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: June 1st 2007, 06:16 PM
  5. Prove by Mathematical Induction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 17th 2007, 10:29 AM

Search Tags


/mathhelpforum @mathhelpforum