# Sequence problem involving inequality

Consider a sequence defined by $\{a_k\}_{k\geq 0}$ , $a_{k+1}=2^k-3a_k$; Find all $a_0$ such that $a_0<a_1<a_2<a_3<\cdots$.

I tried to create some bound on the terms but it doesn't satisfy me, any suggestion would be highly helpful, thanks!

## 4 Answers

Here is a different approach to computing $a_k$.

Let $b_k=a_k(-3)^{-k}$, then we have $$a_{k+1}=2^k-3a_k\implies(-3)^{k+1}b_{k+1}=2^k-3\cdot(-3)^kb_k$$ Dividing by $(-3)^{k+1}$, we get $$b_{k+1}=-\frac13\left(-\frac23\right)^k+b_k$$ We can compute $b_k$ using the formula for the sum of a geometric series: $$b_k=b_0-\frac15\left(1-\left(-\frac23\right)^k\right)$$ Back out the change of variables to get $a_k$ \begin{align} a_k &=(-3)^ka_0-\frac15\left((-3)^k-2^k\right)\\ &=\frac152^k+\left(a_0-\frac15\right)(-3)^k \end{align} As has been noted, this means that the only initial $a_0$ that gives a monotonically increasing sequence $a_k$ is $a_0=\frac15$. For any other value of $a_0$, the factor of $(-3)^k$ will cause oscillation.

Do you know how to solve linear recurrence relations? We're basically looking at an inhomogeneous one of those. It's a lot like a linear differential equation with constant coefficients.

Considering $a_{k+1} + 3a_k = 2^k$ in this way, you first solve the corresponding homogeneous recurrence:

$a_{k+1} + 3a_k=0$

This is solved by the sequence $a_k=A(-3)^k$ for any real $A$. To account for the inhomogenous term, we consider sequences of the form $a_k=A(-3)^k + B(2)^k$. Plugging this into the original recurrence leads to $B=\frac{1}{5}$. Putting in an initial condition, we then find that $A=a_0-\frac{1}{5}$. Thus the formula for our sequence is:

$a_k=\left(a_0-\frac{1}{5}\right)(-3)^k + \frac{1}{5}(2)^k$.

No matter how small a non-zero coefficient we have in front of that oscillating term, it will eventually drown out the growth term. Therefore, the sequence will only keep increasing if $a_0-\frac{1}{5}=0$, i.e., if $a_0=\frac{1}{5}$.

Some playing around with Maple gives the following conjecture: the inequality $a_k<a_{k+1}$ gives an upper bound for $a_0$ when $k$ is even, a lower bound when $k$ is odd, and these bounds converge to a unique solution $$a_0=0.012101210121\cdots$$ in base $3$, that is, $a_0=\frac{16}{80}=\frac{1}{5}$ only. Would love to see if anyone can prove (or disprove) this.

Update. @GTonyJacobs has done so.

Note that:

$a_{k+1}-a_k=2^k-4a_k=4(2^{k-2}-a_k)$. We want $a_0$ such that $a_{k+1}-a_k>0$ for all $k$.

Now can you finish the problem?

• I dont understand what you did ...it would be $a_{k+1}+a_k$ and not $a_{k+1}-a_k$ – ronismofo Feb 10 '14 at 4:48
• That's a mistake. It should be $a_{k+1}-a_k = 2^k-4a_k = 4\left(2^{k-2}-a_k\right)$. – G Tony Jacobs Feb 10 '14 at 4:49
• @user127436: yes- sorry for the mistake. Let me edit my answer. Thanks @G Tony Jacobs – voldemort Feb 10 '14 at 5:04
• is that all??! it directly imply $a_0<\frac 14$ , but it seems like a too trivial to impose in a putnam excersize book; although i am not aware about the answer since the book does not provide one. – ronismofo Feb 10 '14 at 5:18
• It's not quite all. If you use voldemort's inequality for $k=0$, you get $a_0<\frac{1}{4}$, which is true. However, plug in $k=1$. After a couple of steps, you see that this implies $a_0>\frac{1}{6}$. Plugging in $k=2$, we obtain $a_0<\frac{2}{9}$... I'm not sure if this way leads to a solution, but it does lead to an interesting sequence of bounds. – G Tony Jacobs Feb 10 '14 at 5:22