imgur: the simple image sharer
Think I have parts 1 and 2, struggling with the induction :S Any help greatly appreciated!
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 $\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.
I think that the base case should be $\displaystyle n\ge 4~.$
Have a look at this webpage.
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$.
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.
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?
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.