1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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}$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I dont understand what you did ...it would be $ a_{k+1}+a_k$ and not $a_{k+1}-a_k$ $\endgroup$ – ronismofo Feb 10 '14 at 4:48
  • $\begingroup$ That's a mistake. It should be $a_{k+1}-a_k = 2^k-4a_k = 4\left(2^{k-2}-a_k\right)$. $\endgroup$ – G Tony Jacobs Feb 10 '14 at 4:49
  • $\begingroup$ @user127436: yes- sorry for the mistake. Let me edit my answer. Thanks @G Tony Jacobs $\endgroup$ – voldemort Feb 10 '14 at 5:04
  • $\begingroup$ 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. $\endgroup$ – ronismofo Feb 10 '14 at 5:18
  • $\begingroup$ 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. $\endgroup$ – G Tony Jacobs Feb 10 '14 at 5:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.