Decreasing sequence and prove by contradiction

Question

I have "solved" the following question using prove by contradiction. But it seems a bit off to me:

Let {$x_k$} be a sequence satisfying $x_{k+1}\le(1-\beta)x_k$ for $0\lt\beta\lt 1$, and $x_0\le C$. Prove that $x_k\le \varepsilon$ for all $k\geq \beta^{-1}log(\frac{C}{\varepsilon})$

What I did is as follows:

Assume for all $k\geq \beta^{-1}log(\frac{C}{\varepsilon})$, $x_k\gt \varepsilon$:

$k\geq \beta^{-1}log(\frac{C}{\varepsilon}) \Rightarrow \varepsilon \geq \frac{C}{e^{\beta k}} \Rightarrow x_k \gt \frac{C}{e^{\beta k}}$ and if $k=0 \Rightarrow x_0 \gt C \Rightarrow\Leftarrow$. Thus $x_k \le \varepsilon$ .

The contradiction is one in the assumption of the question. But to me it feels like its not comprehensive enough. I tried arriving at contradiction by proving $x_{k+1} \gt (1-\beta)x_k$ but I arrived at $(1-\beta)x_k \geq \frac{C}{e^{\beta k}}(1-\beta)$ and $x_{k+1} \geq \frac{C}{e^{\beta (k+1)}}$. We can show that $\frac{C}{e^{\beta (k+1)}} \gt \frac{C}{e^{\beta k}}(1-\beta) $ but that will not prove $x_{k+1} \gt (1-\beta)x_k$.

Any ideas about the correctness of the proof or an alternative in case I am wrong?

Answer 1

For an alternative: prove by induction that $x_k \leq (1-\beta)^k C$, then oberve that $(1-\beta)^k C \leq \varepsilon$ implies $x_k \leq \varepsilon$. Solve the inequality: you'll get that it is satisfied for $$k\geq \frac{1}{\ln(1-\beta)}\ln\frac{\varepsilon}{C} = \frac{1}{-\ln(1-\beta)}\ln\frac{C}{\varepsilon}.$$

Now, use the inequality $-\ln(1-\beta) \geq \beta$ (*) to conclude: if $k\geq \frac{1}{\beta}\ln\frac{C}{\varepsilon}$, then in particular $k\geq \frac{1}{-\ln(1-\beta)}\ln\frac{C}{\varepsilon}$., and therefore $x_k \leq \varepsilon$.

(*) follows from $-\ln(1-x) = \sum_{n=1}^\infty \frac{x^n}{n}$, for $\lvert x \rvert < 1$.

Answer 2

Unfortunately your proof is logically incorrect, for at least 2 reasons.

Firstly, the assumption you make in the proof is not the negation of what you are trying to prove. The correct assumption to make is \begin{equation*} \mbox{For some} \ k \geq \beta^{-1}\log (C/\epsilon), x_k > \epsilon. \end{equation*}

Secondly, substituting $k=0$ in the last step of your proof is unwarranted, since you have assumed $k \geq \beta^{-1}\log (C/\epsilon)$.