1. Combinatorics Induction Proof

imgur: the simple image sharer

Think I have parts 1 and 2, struggling with the induction :S Any help greatly appreciated!

2. Re: Combinatorics Induction Proof

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.

3. 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

4. Re: Combinatorics Induction Proof

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.

5. 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$.

6. Re: Combinatorics Induction Proof

Thanks for the help - where am I going wrong?

7. Re: Combinatorics Induction Proof

Originally Posted by TheManFromScot

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.

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 :/

9. Re: Combinatorics Induction Proof

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$.

10. 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

11. Re: Combinatorics Induction Proof

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?

12. 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

13. Re: Combinatorics Induction Proof

Turns out my question 2b falls apart :/

Can anyone shed some light on this?

Thank you

14. Re: Combinatorics Induction Proof

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.

15. 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