find the closed form of $a_n=3a_{\lceil n/2 \rceil}+1$, $a_1=1$

Let $a_1,a_2,...$ be the sequence recursively deﬁned 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$.

• Yesterday I wanted to post the same answer you have! (+1). – Mhenni Benghorbal Mar 26 '16 at 19:38

HINTS: First, notice how $a_1$ (is by itself, forget it); $a_2$ = $a_3$; $a_4 = \cdots = a_7$; ... So, show by induction that for every $k \ge 0$, the elements in the sequence with index from $2^k$ to $2^{k+1}-1$ are equal. So you really only need to get the elements $a_{2^k}$. Call these $b_k$; then derive the recurrence equation for $b_k$ and solve it.

• Small mistake. It's ceiling but not floor, $a_3=3a_2 +1$. So it should be sequence of $n$ from $2^k+1$ to $2^{k+1}$ (except $a_1,a_2$) – lEm Mar 26 '16 at 2:59
• OK - same hints. By the way, $a_2$ is not an exception; it is the subsequence of $n$ from $2^0+1$ to $2^{0+1}$. – mathguy Mar 26 '16 at 3:22