Finding the general formula for the sequence with $d_0=1$, $d_1=-1$, and $d_k=4 d_{k-2}$

Question

Suppose that we want to find a general formula for the terms of the sequence

$$d_k=4 d_{k-2}, \text{ where } d_0=1 \text{ and } d_1=-1$$

I have done the following:

\begin{align*}d_k=4d_{k-2}&=2^2d_{k-2} \\ &=2^2\left (2^2d_{(k-2)-2}\right )=2^4d_{k-4} \\ & =2^4\left (2^2d_{(k-4)-2}\right )=2^6d_{k-6} \\ & = 2^6\left (2^2d_{(k-6)-2}\right )=2^8d_{k-8} \\ & = \ldots \\ & = 2^id_{k-i}\ , \ \ i \text{ even}\end{align*}

If $k$ even, then at the last step we have for $i=k$ (since $k$ is the maximum even number $\leq k$) : $d_k=2^kd_{k-k}=2^kd_0=2^k$.

If $k$ odd, then at the last step we have for $i=k-1$ (since $k-1$ is the maximum even number $\leq k$) : $d_k=2^{k-1}d_{k-(k-1)}=2^{k-1}d_1=-2^{k-1}$.

How can we find the general form for the terms of the recurrence relation? Or do we distinguish cases when $k$ is even and odd?

I am interested to find the general formula without using the characteristic equation.

Answer 1

You found $d_k=2^k$ when $k$ is even and $d_k=-2^{k-1}$ when $k$ is odd.

To put this in one formula, note that $\dfrac{1+(-1)^n}2$ is $0$ when $n$ is odd and $1$ when $n$ is even,

whereas $\dfrac{1-(-1)^n}2$ is $1$ when $n$ is odd and $0$ when $n$ is even.

So you could say $d_k=2^k\dfrac{1+(-1)^k}2-2^{k-1}\dfrac{1-(-1)^k}2,$

which simplifies to $2^{k-2}\left[1+3(-1)^k\right]$.

Answer 2

You have that even indexes and odd indexes are completely independent so the problem is basically equivalent to two problems of the form $u_{k+1} = 4 u_k$ with two different initial conditions.

So let's first solve this last problem. It's easy to check that the solution must be in the form $u_k = u_0 \,4^k$.

If $u_0=1$ the solution is then $u_k = 4^k$ and for $u_0 = -1$ it's $u_k = -4^k$.

Here you have that the sequence $d_{2k}$ is like the $u$ which started at 1 and the $d_{2k+1}$ is the $u$ which starts at $-1$. So in short you can rewrite $$d_k = (-1)^k 4^{\lfloor k/2\rfloor}\,$$ where $\lfloor \cdot \rfloor$ is the integer part (floor) of a number.