# Tag Info

2

HINT : Dividing the both sides by $3^n$ gives $$\frac{a_n}{3^n}=\frac{a_{n-1}}{3^{n-1}}+\frac{1}{4}\cdot\left(\frac 43\right)^n\iff b_n-b_{n-1}=\frac{1}{4}\cdot\left(\frac 43\right)^n$$ where $b_n=\frac{a_n}{3^n}$.

2

Firstly, an equation does not have time complexity. What you should ask is the asymptotic complexity of $T(n)$ as $n \to \infty$, where $T$ satisfies the given equation for any natural $n$. To get an idea of what the answer should be, iteratively bound it. You presumably are given that $T(n) \ge 0$, otherwise things won't work. $\def\nn{\mathbb{N}}$ ...

2

Upon your request I computed the first $10\,000$ of the $a_k$ using Mathematica. Here is the output: Note that the figure contains two graphs.

1

This is indeed a non-homogeneous relation, the simplest you can think of. Starting from $$a_1=a_0+c,$$ you have $$a_2=a_1+c=a_0+2c,\\ a_3=a_2+c=a_0+3c\\ a_4=a_3+c=a_0+4c\\\cdots$$ Do I need to continue ? The standard way to solve a linear recurrence is by solving the homogeneous equation $$a_n=a_{n-1},$$ i.e. by recurrence $$a_n=a_0.$$ finding a ...

1

You can first calculate the first terms of this sequence. $$\begin{array}{rclclcl} a_1&=&a_0+c &&&&\\ a_2&=&a_1+c &=& a_0+c+c &=& a_0+2c \\ a_3&=&a_2+c&=& a_0+2c+c &=& a_0+3c \\ a_4&=&a_3+c&=& a_0+3c+c &=& a_0+4c \\ \end{array}$$ Do you see a pattern? Can you ...

1

Let $n=2^{2^k}$ with $k>0$ ; $n$ is a perfect square. Then, $$T(2^{2^k})=2T(2^{2^{k-1}})+1,$$ which can be written $$U(k)=2U(k-1)+1.$$ The general solution is $$U(k)=C2^k-1,$$ or $$T(n)=C\lg(n)-1.$$ Check: $$C\ln(n)-1=2(C\lg(\sqrt n)-1).$$

1

You have $$a_{n} = 3~a_{n-1} + 4^{n-1} \tag{X}$$ and $$a_{n+1} = 3~a_{n} + 4\cdot 4^{n-1} \tag{Y}$$ Compute $Y - 4X$ and you'll have a basic linear recurrence.

1

Hint. A particular solution is $a_n^{(p)}=4^n$.

Only top voted, non community-wiki answers of a minimum length are eligible