Results 1 to 15 of 15

Math Help - Combinatorics Induction Proof

  1. #1
    Newbie
    Joined
    Sep 2013
    From
    Glasgow
    Posts
    8

    Combinatorics Induction Proof

    imgur: the simple image sharer

    Think I have parts 1 and 2, struggling with the induction :S Any help greatly appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1

    Re: Combinatorics Induction Proof

    Quote Originally Posted by TheManFromScot View Post
    imgur: the simple image sharer
    Think I have parts 1 and 2, struggling with the induction :S Any help greatly appreciated!
    I think that I must be reading the question incorrectly.

    Does is say if {a_n} = \sum\limits_{k = 0}^n {{\binom{n}{k}^{ - 1}}} prove {a_n} > 2 + \frac{2}{n}~?.

    That is not true for even the base case. So I must have it wrong. Please advise.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2013
    From
    Glasgow
    Posts
    8

    Re: Combinatorics Induction Proof

    I am guessing so.. I really can't fathom it out.. When n=1, An = 2 which isn't greater than 4 is as far as I got
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1

    Re: Combinatorics Induction Proof

    Quote Originally Posted by TheManFromScot View Post
    I am guessing so.. I really can't fathom it out.. When n=1, An = 2 which isn't greater than 4 is as far as I got
    I think that the base case should be n\ge 4~.

    Have a look at this webpage.
    Last edited by Plato; September 20th 2013 at 12:50 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member FelixFelicis28's Avatar
    Joined
    Jan 2013
    From
    Edinburgh, United Kingdom
    Posts
    70
    Thanks
    32

    Re: Combinatorics Induction Proof

    There is no need for induction on this question when you can prove it simply by re-writing the inequality but very well...

    I am going to assume there was a misprint and they omitted that the result holds true for n\geq 4.

    OP, from your induction hypothesis, you have a_k > 2 + \tfrac{2}{k} for k \geq 4 and you wish to show with the assumption that a_{k+1} > 2 + \tfrac{2}{k+1}.

    Now, recall that a_{k+1} = \frac{k+2}{2(k+1)} a_k + 1.

    Multiply the inequality a_k > 2 + \frac{2}{k} through by \frac{k+2}{2(k+1)} and the result falls out fairly quickly with some manipulation.

    @Plato, I think you mean for n \geq 4 as equality holds for n=3.
    Last edited by FelixFelicis28; September 20th 2013 at 12:47 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Sep 2013
    From
    Glasgow
    Posts
    8

    Re: Combinatorics Induction Proof

    Combinatorics Induction Proof-photo.jpg

    Thanks for the help - where am I going wrong?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member FelixFelicis28's Avatar
    Joined
    Jan 2013
    From
    Edinburgh, United Kingdom
    Posts
    70
    Thanks
    32

    Re: Combinatorics Induction Proof

    Quote Originally Posted by TheManFromScot View Post
    Click image for larger version. 

Name:	photo.jpg 
Views:	8 
Size:	1.05 MB 
ID:	29221

    Thanks for the help - where am I going wrong?
    No problem. There's nothing wrong with your working, you just need to do a bit of deduction for the last bit.

    Clearly for k\geq 4, \ k + 1 > k \implies \frac{1}{k} > \frac{1}{k+1} \implies 2 + \frac{2}{k} > 2+ \frac{2}{k+1}

    Also, this may be pedantic but I think you could make it a bit clearer that what you've done is that you've taken your inductive assumption and you've multiplied that through by \frac{k+1}{2(k+1)} and then added 1.
    Last edited by FelixFelicis28; September 21st 2013 at 09:32 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Sep 2013
    From
    Glasgow
    Posts
    8

    Re: Combinatorics Induction Proof

    Thank you very much!

    I;ve had a look at part (d) and tried a sort of reverse induction. I really think I am overly complicating it though :/
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member FelixFelicis28's Avatar
    Joined
    Jan 2013
    From
    Edinburgh, United Kingdom
    Posts
    70
    Thanks
    32

    Re: Combinatorics Induction Proof

    Quote Originally Posted by TheManFromScot View Post
    Thank you very much!

    I;ve had a look at part (d) and tried a sort of reverse induction. I really think I am overly complicating it though :/
    If a_{n+1} < a_n \Leftarrow a_{n+1} - a_n < 0 \Leftarrow \frac{n+2}{2(n+1)} a_n + 1 - a_n < 0

    Clearly it is sufficient to prove the rightmost inequality.

    Also, note a_{n+1} < a_n iff n\geq 4.
    Last edited by FelixFelicis28; September 22nd 2013 at 05:51 AM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Sep 2013
    From
    Glasgow
    Posts
    8

    Re: Combinatorics Induction Proof

    Though I am following the logic, these are jumps I'd never considered.. Now I can;t even manipulate haha! This is quite clearly beyond me, though thank you very much for the input
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member FelixFelicis28's Avatar
    Joined
    Jan 2013
    From
    Edinburgh, United Kingdom
    Posts
    70
    Thanks
    32

    Re: Combinatorics Induction Proof

    Quote Originally Posted by TheManFromScot View Post
    Though I am following the logic, these are jumps I'd never considered.. Now I can;t even manipulate haha! This is quite clearly beyond me, though thank you very much for the input
    It's not beyond you, just keep going at it! Practice makes pefect.

    Clearly if a_{n+1} < a_n \implies a_{n+1} - a_n < 0.

    Substitute a_{n+1} = \frac{n+2}{2(n+1)} a_n + 1 for a_{n+1} and then you have the rightmost inequality in my above post. You will be able to simplify that down into a fraction, call it \alpha. The denominator of \alpha will clearly be 2(n+1) and 2(n+1) > 0 \ \forall n \geq 4 so clearly \alpha < 0 iff the numerator of \alpha < 0. Try it, you'll be able to sneak in the result from part C.

    Also, I see you're a fellow Scot! Are you studying Mathematics @ Glasgow?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Sep 2013
    From
    Glasgow
    Posts
    8

    Re: Combinatorics Induction Proof

    Thank you very much think I have this one sorted now! I'm not living in Glasgow now, have travelled over the border - can never lose my Scottish roots though, haha
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Sep 2013
    From
    Glasgow
    Posts
    8

    Re: Combinatorics Induction Proof

    Turns out my question 2b falls apart :/

    Can anyone shed some light on this?

    Thank you
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Junior Member FelixFelicis28's Avatar
    Joined
    Jan 2013
    From
    Edinburgh, United Kingdom
    Posts
    70
    Thanks
    32

    Re: Combinatorics Induction Proof

    Quote Originally Posted by TheManFromScot View Post
    Turns out my question 2b falls apart :/

    Can anyone shed some light on this?

    Thank you
    Hello again.

    2b)

    We have:

    a_n = \sum_{k=0}^n \binom{n}{k}^{-1}

    and we wish to show a_{n} = \tfrac{n+1}{2n} a_{n-1} + 1, that is:

    \sum_{k=0}^n \binom{n}{k}^{-1} = \frac{n+1}{2n} \sum_{k=0}^{n-1} \binom{n-1}{k}^{-1} + 1

    Now, we proceed by writing:

    \displaystyle \begin{aligned} a_n = \sum_{k=0}^n \binom{n}{k}^{-1} & = 1 + \sum_{k=1}^n \left[\binom{n}{k}\right]^{-1} \\ & = 1 + \sum_{k=1}^n \left[\frac{n}{k}\binom{n-1}{k-1}\right]^{-1} \\ & = 1 + \frac{1}{n} \sum_{k=1}^{n} k \binom{n-1}{k-1}^{-1} \end{aligned}

    Now, we shift the summation index and re-write it as:

    1 + \frac{1}{n} \sum_{k=1}^n k \binom{n-1}{k-1}^{-1} = 1 + \frac{1}{n} \sum_{k=0}^{n-1} (k+1) \binom{n-1}{k}^{-1}

    Now, clearly:


    k \binom{n}{k}^{-1} = (n-k) \binom{n}{k}^{-1}
    Thus

    a_n = 1 + \frac{1}{n} \sum_{k=0}^{n-1} (k+1) \binom{n-1}{k}^{-1} = 1 + \frac{1}{n} \sum_{k=0}^{n-1} (n-k) \binom{n-1}{k}^{-1}

    Adding these two series, we get:

    2a_n = 2 + \frac{1}{n} \sum_{k=0}^{n-1} (n+1) \binom{n-1}{k}^{-1}

    I'll let you finish off the rest.
    Last edited by FelixFelicis28; September 25th 2013 at 11:07 PM.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Newbie
    Joined
    Sep 2013
    From
    Glasgow
    Posts
    8

    Re: Combinatorics Induction Proof

    Hi again Thank you very much for the reply, but I managed to readjust my previous method - this involved accounting for the middle term when 'n' is odd, and readjusting - your method is much easier on the eye
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Induction question - combinatorics
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: October 8th 2010, 02:43 AM
  2. Combinatorics proof help
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 3rd 2010, 06:09 AM
  3. Combinatorics Proof?
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 24th 2009, 10:10 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  5. Combinatorics Proof
    Posted in the Statistics Forum
    Replies: 1
    Last Post: March 27th 2007, 09:36 AM

Search Tags


/mathhelpforum @mathhelpforum