Tuesday, 11 April 2017

discrete mathematics - Help finishing proof via induction for a summation



So I have to prove the following equation using induction for n >= 2:
$$
\sum\limits_{i=1}^n 4/5^i < 1
$$
However the question asks me to prove something stronger such as this:

$$
\sum\limits_{i=1}^n 4/5^i <= 1 - \frac{1}{5^n}
$$
first to imply the first equation is true.
So far I have the following:



Base Case:
Let n = 2



$$

\sum\limits_{i=1}^2 4/5^i = \frac{4}{5} + \frac{4}{25} = \frac {24}{25}
$$
then I also applied it to
$$ 1 - \frac{1}{5^n} \rightarrow 1 - \frac{1}{5^2} = \frac{24}{25}$$
Therefore I can make the following assumptions yes?



Inductive Hypothesis
for all 2 <= n <= k it is
$$
\sum\limits_{i=1}^n 4/5^i = 4\frac{\frac{1}{5^n} - 1}{\frac{1}{5} - 1} = 1 - \frac{1}{5^n} < 1

$$
Inductive Step
Hopefully I'm ok up to here, I'll show what I have so far for this step.
$$
\sum\limits_{i=1}^{k+1} 4/5^i = \frac{\frac{1}{5^{k+1}} - 1}{\frac{1}{5} - 1} = 4\frac{(\frac{1}{5^k}-1) * \frac{1}{5} - \frac{4}{5}}{\frac{1}{5} -1} $$
$$
= \frac{1}{5} * 4\frac{(\frac{1}{5^k}) - 1}{\frac{1}{5} -1} - 4\frac{\frac{4}{5}}{\frac{1}{5} - 1}
$$
so here I have:
$$

4\frac{(\frac{1}{5^k}) - 1}{\frac{1}{5} -1}
$$
which I know is:
$$
= \sum\limits_{i=1}^k 4/5^i
$$
which is my inductive hypothesis, I am unsure of how to finish my proof from here... any help correcting or finishing the proof is very much appreciated


Answer



Hint:
$$\sum_{i=1}^{k+1}4/5^i=\sum_{i=1}^k 4/5^i+4/5^{k+1}$$

Use the induction hypothesis on the sum from $1$ to $k$ and simplify.


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...