imgur: the simple image sharer

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

Printable View

- Sep 20th 2013, 11:05 AMTheManFromScotCombinatorics 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 AMPlatoRe: Combinatorics Induction Proof
I think that I must be reading the question incorrectly.

Does is say if $\displaystyle {a_n} = \sum\limits_{k = 0}^n {{\binom{n}{k}^{ - 1}}} $ prove $\displaystyle {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 PMTheManFromScotRe: 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 PMPlatoRe: Combinatorics Induction Proof
I think that the base case should be $\displaystyle n\ge 4~.$

Have a look at this webpage. - Sep 20th 2013, 12:42 PMFelixFelicis28Re: 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 $\displaystyle n\geq 4$.

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

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

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

@Plato, I think you mean for $\displaystyle n \geq 4$ as equality holds for $\displaystyle n=3$. - Sep 21st 2013, 05:41 AMTheManFromScotRe: Combinatorics Induction Proof
Attachment 29221

Thanks for the help - where am I going wrong? - Sep 21st 2013, 09:30 AMFelixFelicis28Re: Combinatorics Induction Proof
No problem. There's nothing wrong with your working, you just need to do a bit of deduction for the last bit.

Clearly for $\displaystyle 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 $\displaystyle \frac{k+1}{2(k+1)}$ and then added 1. - Sep 22nd 2013, 02:54 AMTheManFromScotRe: 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 AMFelixFelicis28Re: Combinatorics Induction Proof
- Sep 22nd 2013, 06:12 AMTheManFromScotRe: 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 AMFelixFelicis28Re: Combinatorics Induction Proof
It's not beyond you, just keep going at it! Practice makes pefect. ;)

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

Substitute $\displaystyle a_{n+1} = \frac{n+2}{2(n+1)} a_n + 1$ for $\displaystyle 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 $\displaystyle \alpha$. The denominator of $\displaystyle \alpha$ will clearly be $\displaystyle 2(n+1)$ and $\displaystyle 2(n+1) > 0 \ \forall n \geq 4$ so clearly $\displaystyle \alpha < 0$ iff the numerator of $\displaystyle \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 AMTheManFromScotRe: 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 AMTheManFromScotRe: Combinatorics Induction Proof
Turns out my question 2b falls apart :/

Can anyone shed some light on this?

Thank you - Sep 25th 2013, 10:49 PMFelixFelicis28Re: Combinatorics Induction Proof
Hello again. :)

2b)

We have:

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

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

$\displaystyle \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 \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:

$\displaystyle 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:

Thus

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

$\displaystyle 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:

$\displaystyle 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 PMTheManFromScotRe: 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