# Combinatorics Induction Proof

• Sep 20th 2013, 11:05 AM
TheManFromScot
Combinatorics Induction Proof
imgur: the simple image sharer

Think I have parts 1 and 2, struggling with the induction :S Any help greatly appreciated!
• Sep 20th 2013, 11:41 AM
Plato
Re: Combinatorics Induction Proof
Quote:

Originally Posted by TheManFromScot
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.
• Sep 20th 2013, 12:12 PM
TheManFromScot
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
• Sep 20th 2013, 12:16 PM
Plato
Re: Combinatorics Induction Proof
Quote:

Originally Posted by TheManFromScot
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.
• Sep 20th 2013, 12:42 PM
FelixFelicis28
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$.
• Sep 21st 2013, 05:41 AM
TheManFromScot
Re: Combinatorics Induction Proof
Attachment 29221

Thanks for the help - where am I going wrong?
• Sep 21st 2013, 09:30 AM
FelixFelicis28
Re: Combinatorics Induction Proof
Quote:

Originally Posted by TheManFromScot
Attachment 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.
• Sep 22nd 2013, 02:54 AM
TheManFromScot
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 :/
• Sep 22nd 2013, 05:31 AM
FelixFelicis28
Re: Combinatorics Induction Proof
Quote:

Originally Posted by TheManFromScot
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$.
• Sep 22nd 2013, 06:12 AM
TheManFromScot
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
• Sep 22nd 2013, 06:18 AM
FelixFelicis28
Re: Combinatorics Induction Proof
Quote:

Originally Posted by TheManFromScot
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?
• Sep 23rd 2013, 07:42 AM
TheManFromScot
Re: Combinatorics Induction Proof
Thank you very much :D 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
• Sep 25th 2013, 10:34 AM
TheManFromScot
Re: Combinatorics Induction Proof
Turns out my question 2b falls apart :/

Can anyone shed some light on this?

Thank you
• Sep 25th 2013, 10:49 PM
FelixFelicis28
Re: Combinatorics Induction Proof
Quote:

Originally Posted by TheManFromScot
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. ;)
• Sep 25th 2013, 11:33 PM
TheManFromScot
Re: Combinatorics Induction Proof
Hi again :D 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