I'm trying to find a closed form for the following recurrence relation:
$$ \begin{align} a_0 &= 0\\ a_{n+1} &= a_n + \bigg\lfloor \frac {a_n} 2 \bigg\rfloor + 1 &\text{for } n \geq 0\\ &= \frac 3 2 a_n + \begin{cases} 1 &\text{if } a_n \text{ is even}\\ \frac 1 2 &\text{if } a_n \text{ is odd} \end{cases}\\ &= \frac 3 2 a_n + \bigg(\frac 1 2\bigg)^{a_n \bmod 2}\\ &= \frac 3 2 a_n + 1 - \frac {a_n \bmod 2} 2\\ &= \frac 3 2 a_n + \frac 1 4 \cos (\pi a_n) + \frac 3 4 \end{align} $$
I wrote $a_{n+1}$ in $5$ different ways hoping one of the ways would make it easier to find a closed form.
I'm using the method in $1.1$ of "generatingfunctionology" by Wilf:
Define $A(x) = \sum_{n \geq 0} a_n x^n$. Take the LHS of any of the $a_{n+1} = ...$ relations and multiply it by $\sum_{n \geq 0} x^n$. We get:
$$ \begin{align*} \sum_{n \geq 0} a_{n+1} x^n &= a_1 + a_2 x + a_3 x^2 + a_4 x^3 + ...\\ &= \{(a_0 + a_1 x + a_2 x^2 + a_3 x^3 + a_4 x^4 + ...) - a_0 \} / x\\ &= A(x) / x \end{align*} $$
since $a_0 = 0$.
Now, do the same to the RHS of one of the $a_{n+1} = ...$ relations. Let's use expression $(4)$:
$$ \begin{align*} \sum_{n \geq 0} \bigg(\frac 3 2 a_n + \bigg(\frac 1 2\bigg)^{a_n \bmod 2}\bigg) x^n &= \frac 3 2 \sum_{n \geq 0} a_n x^n + \sum_{n \geq 0} \bigg(\frac 1 2\bigg)^{a_n \bmod 2} x^n\\ &= \frac 3 2 A(x) + \sum_{n \geq 0} \bigg(\frac 1 2\bigg)^{a_n \bmod 2} x^n \end{align*} $$
And if I use expression $(5)$ instead, I get:
$$ \begin{align*} &\frac 3 2 A(x) + \sum_{n \geq 0} \bigg(1 - \frac {a_n \bmod 2} 2\bigg) x^n\\ = &\frac 3 2 A(x) + \frac 1 {1 - x} + \frac 1 2 \sum_{n \geq 0} ( a_n \bmod 2) x^n \end{align*} $$
wherein we have used the familiar geometric series evaluation $\sum_{n \geq 0} x^n = \frac 1 {1 − x}$, which is valid for $|x| < 1$.
If I use expression $(6)$ instead, I get:
$$ \begin{align*} &\frac 3 2 A(x) + \sum_{n \geq 0} \bigg(\frac 1 4 \cos (\pi a_n) + \frac 3 4\bigg) x^n\\ = &\frac 3 2 A(x) + \frac 1 4 \sum_{n \geq 0} \cos (\pi a_n) x^n + \frac 3 4 \sum_{n \geq 0} x_n\\ = &\frac 3 2 A(x) + \frac 1 4 \sum_{n \geq 0} \cos (\pi a_n) x^n + \frac 3 4 \bigg(\frac 1 {1 - x}\bigg) \end{align*} $$
And this is where I am stuck, since I am not able to simplify away the remaining $a_n$ in any of the RHS's (Right Hand Sides).
The furthest I get is that:
$$ \begin{align*} A(x) \bigg(1 - \frac 3 2 x\bigg) &= \sum_{n \geq 0} \bigg(\frac 1 2\bigg)^{a_n \bmod 2} x^{n+1}\\ &= \frac x {1 - x} + \frac 1 2 \sum_{n \geq 0} ( a_n \bmod 2) x^{n+1}\\ &= \frac 1 4 \sum_{n \geq 0} \cos (\pi a_n) x^{n+1} + \frac 3 4 \bigg(\frac x {1 - x}\bigg) \end{align*} $$
Written with StackEdit.