Closed-form expression $(x_{2^l})_{l\in \mathbb{N}_0}$

Question

I have this problem I'm not sure how to solve.

Given $x \in \mathbb{R}^{\mathbb{N}_0}_{\geq 0}$ and

$x_k=\left\{\begin{matrix} 0 & k=0\\ 4x_{\left \lfloor \frac{k}{2} > \right \rfloor} + k^2 & k \in \mathbb{N} \end{matrix}\right.$

Determine a closed-form expression for $(x_{2^l})_{l\in > \mathbb{N}_0}$.

My solution attempt is as follows.

For $k \in \mathbb{N}$ we have $x_k=4x_{\left \lfloor \frac{k}{2} \right \rfloor} + k^2$. It follows

$$x_{2k}=4x_{\left \lfloor \frac{2k}{2} \right \rfloor} + 2k^2$$ $$=4x_{k} + 2k^2$$

For $l \in \mathbb{N}_0$ it follows

$$x_{2^{l+1}}=x_{2*2^l}=4x_{2^l} + 2 * 2^{2l}=4x_{2^l} + 2^{2l+1}$$

Is this correct? And how to get $x_{2^l}$ from here?

Answer 1

Your calculation should be revised. We obtain for $l\in\mathbb{N}_0$: \begin{align*} x_{2^{l+1}}=4x_{2^l}+\color{blue}{\left(2^{l+1}\right)^2}=4x_{2^l}+4^{l+1} \end{align*}

We start with $k=2^l$, calculate a few iterations and look if we can make a good guess of a closed formula. The validity of the formula could then be shown for instance with a proof by induction.

We obtain by successively using the recursion formula \begin{align*} \color{blue}{x_{2^l}}&=4x_{2^{l-1}}+\left(2^l\right)^2\\ &=4x_{2^{l-1}}+4^l=4\left(4x_{2^{l-2}}+\left(2^{l-1}\right)^2\right)+4^l=4^2x_{2^{l-2}}+4\cdot 4^{l-1}+4^l\tag{1}\\ &=4^2x_{2^{l-2}}+2\cdot 4^l=4^2\left(4x_{2^{l-3}}+\left(2^{l-2}\right)^2\right)+2\cdot4^l =4^3x_{2^{l-3}}+4^2\cdot4^{l-2}+2\cdot 4^l\\ &=4^3x_{2^{l-3}}+3\cdot 4^l\\ &\qquad\vdots\\ &\color{blue}{=4^lx_{2^0}+l\cdot 4^l}\tag{2} \end{align*}

Comment:

• In (1) we use the recursion formula once and do the same in the next line.

• In (2) we see the relationship between exponents and indices expressed in $l-1,l-2,l-3$ in the first lines and obtain the representation in the last line by setting $l-l$.

Since $x_0=0$ and $$x_1=4x_0+1=4\cdot0+1=1$$ we obtain \begin{align*} \color{blue}{x_{2^l}}=4^lx_{2^0}+l\cdot 4^l=4^l+l\cdot 4^l=\color{blue}{(l+1)4^l} \end{align*}