Let $a_1,a_2,...$ be the sequence recursively defined by $a_1 = 1$ and $a_n = 3a_{\lceil n/2 \rceil}+ 1$ for $n \geq 2$.
a)Find $a_2,a_3,a_4,a_5,a_6,a_7$and $a_8$
b)Guess a formula for $ a_n $
$a_1=1,a_2=4,a_3=13,a_4=13,a_5=40,a_6=40,a_7=40,a_8=40$ is the start of the sequence i found.
I've tried $3^{\lceil n/2 \rceil}+1$ and other forms similar to $3^n$
I can't find a formula which works any ideas?
OK - not sure if you were able to use the hint.
Let $b_k = a_{2^k}$. I assume you are able to show, by induction, that $a_n = b_k$ for all $n$ from $2^k$ to $2^{k+1}-1$. Then note that this means $a_n = b_{\lfloor \log_2 n \rfloor}$ for all $n \ge 1$.
So we only need to compute the $b_k$ and note it makes sense to start with $k = 0$. We have $b_0 = 1, b_{k+1} = 3 b_k + 1$. Then also $b_{k+2} = 3 b_{k+1} + 1$; subtract side by side to get $b_{k+2} - b_{k+1} = 3(b_{k+1} -b_k)$. This means the successive differences form a geometric progression with ratio 3. That is: $b_1 - b_0 = 3$ (directly from $b_0 = 1$ and $b_1 = 4$), then $b_2 - b_1 = 9$, etc.
Now $b_k = b_0 + (b_1 - b_0) + \cdots + (b_k - b_{k-1}) = 1 + 3 + \cdots + 3^k = \dfrac {3^{k+1}-1} 2$.
So finally: $a_n = \dfrac {3^{\lfloor \log_2 n \rfloor + 1} - 1 } 2$.
