Help with a recurrence with even and odd terms [duplicate]
I have the following recurrence that I've been pounding on:
$$ a(0)=1\\ a(1)=1\\ a(2)=2\\ a(2n)=a(n)+a(n+1)+n\ \ \ (\forall n>1)\\ a(2n+1)=a(n)+a(n-1)+1\ \ \ (\forall n\ge 1) $$
I don't have much background in solving these things, so I've been googling around looking for different techniques. Unfortunately, I haven't been able to correctly apply them yet. So far I've tried:
- Characteristic equations
- Generating functions
- Plugging it into Wolfram Alpha
- Telescoping
- Observation
I'm sure that one or more of these is the way to go, but my biggest problem right now is figuring out how to deal with the idea that there are different equations for odd and even values of $n$. I'm not necessarily looking for a solution (though it would be gratefully accepted), but any nudges in the right direction would be much appreciated.
To follow up, it turned out that the speed problem described in my comment, below was related to the Decimal implementation in Python 2.7. Switching to Python 3.3 (and Java) made everything many orders of magnitude better.
Solution 1:
I have an almost closed form. It uses the functions $z_2(n)$, which is the number of zeros in the binary representation of $n$ (after the first non-zero digit, of course) and $Z_2(n)=\sum_{i=1}^n z_2(n)$. I am quite sure these can be calculated quickly, but I'll leave that to you.
Section 1: A Closed Form For S(n).
Running off of Michael Biro's answer, where they define $S(n)=a(n+2)-a(n)$ and calculate that $S(2n)=S(n)+1$ and $S(2n+1)=S(n-1)$, we can find a closed form for $S$ and then find a neat sum for it.
In particular, rewrite Michaels two properties as: $$S(n)=S(2n+3)=S(2n)-1.$$ and consider that this measures the numbers of even numbers we pass through as we iterate the function $f(2n+3)=n$ and $f(2n)=n$. We also have the edge conditions $$S(0)=1$$ $$S(1)=2$$ $$S(2)=5$$ Now, this relation is clearly dealing with something happening in binary - but even better than binary is to write $n$ in base $2$, leading with the digit $1$ or $3$ and otherwise using the digits $0$ and $3$ - meaning that the expansion of $2n$ is the expansion of $n$, with a $0$ appended, and the expansion of $2n+3$ is the expansion of $n$ with a $3$ appended. This means that the map $f$ just chops off the last digits of this representation! A table of such representations follows: \begin{array}{ll} n & n_2 \\ 1 & 1 \\ 2 & 10 \\ 3 & 3 \\ 4 & 100 \\ 5 & 13 \\ 6 & 30 \\ 7 & 103 \\ 8 & 1000 \\ 9 & 33 \\ 10 & 130 \\ 11 & 1003 \\ 12 & 300 \\ 13 & 133 \\ 14 & 1030 \\ 15 & 303 \\ 16 & 10000 \\ 17 & 1033 \\ \end{array} What is notable is that if the pattern starts with "3", then it will iterate to $0$ under $f$ after some number of steps, meaning $S(n)$ would be the number of $0$s in the expansion (how many times the orbit of $n$ under $f$ passed through even numbers), plus $S(0)=1$. If the pattern starts with "10", then $n$ first passes through $2$ under $f$, so $S(n)$ would be the number of zeros in the expansion (excluding the first one used in the pattern "10") plus $S(2)=5$. If the pattern starts with "13", then $n$ passes through $1$ under $f$ and so $S(n)$ equals the number of zeros in the pattern, plus $S(1)=2$.
This looks kind of intimidating to start with, but it's actually not too bad. Notice that if we chop off the most significant digit of our representation, the resulting representation is divisible by $3$, since it only uses the digits $0$ and $3$ and, moreover, if we divide that by $3$ and write it in normal binary, it's the same as if we replaced every $3$ by a $1$. Therefore, if we let $z_2(n)$ be the number of zeros in the normal binary representation of $n$, then we can interpret the above as follows, letting $2^b$ be the place value of the $1$ in our representation of $n$ if it exists (which must happen if $3$ doesn't divide $n$): $$S(n)=\begin{cases}z_2\left(\frac{n}3\right)+1&&\text{if }n\equiv 0\pmod 3 \\ z_2\left(\frac{n+2\cdot 2^b}3\right)+2&&\text{if }5\cdot 2^{b-1} \leq n \\ z_2\left(\frac{n+2\cdot 2^b}3\right)+4&&\text{if }n < 5\cdot 2^{b-1}\end{cases}$$ where we add $2\cdot 2^b$ to $n$ to convert the first digit from a $1$ to a $3$ and the condition that $5\cdot 2^{b-1}\leq n$ is equivalent to the expansion of $n$ beginning with "13". We require knowing $b$ to calculate the above, but noticing that we must have that $$n=2^b+3\cdot k$$ for some $0\leq k \leq 2^b-1$, implying $2^b\leq n \leq 4\cdot 2^b - 3$, it is obvious that $b$ must either be $\lfloor\log_2(n)\rfloor$ or $\lfloor\log_2(n)\rfloor-1$ and that $n-2^b$ is divisible by $3$. So, we could write: $$b=\begin{cases}\lfloor\log_2(n)\rfloor && \text{if }2^{\lfloor\log_2(n)\rfloor}\equiv n\pmod 3\\\lfloor\log_2(n)\rfloor-1 && \text{if }2^{\lfloor\log_2(n)\rfloor-1}\equiv n\pmod 3\end{cases}.$$
We could quickly write the expansion of some large integer using this information. Say we wanted to know the representation of $124315$ which is $1$ mod $3$ and is between $2^{16}$ and $2^{17}-1$ so $b'=16$. We note that $124315-2^{16}$ is divisible by $3$, so we know our expansion will have a $1$ in the $2^{16}$ position followed by the binary representation of $\frac{124315-2^{16}}3=1110010110011011_2$ with $1$'s replaced by $3$'s. This gives: $$124315=13330030330033033_2$$
Section 2: A Closed Form For $a(n)$
We are going to have to split into cases for this, which is annoying. In particular, from the definition of $S$, we obviously have: $$a(2n)=1+\sum_{i=0}^{n-1}S(2i)$$ $$a(2n+1)=1+\sum_{i=0}^{n-1}S(2i+1)$$ Let's start with the even case because it works out more nicely. In particular, let's rewrite $S(2i)=S(i)+1$ and get: $$a(2n)=1+\sum_{i=0}^{n-1}S(i)+1$$ which means that we are taking the sum of $S$ over all numbers less than $n$. To do this, we just need to find all representations in our system giving a number less than $n$. For convenience, we'll define $[n]$ to be the greatest integer strictly less than $n$ (so $[5]=4$ for instance). Next, we get to four cases
- First, let's list every representation starting with "3". This is equivalent to listing all binary representations less than $\frac{n}3$. So, since $S(3n)=z_2(n)+1$, if we define $$Z_2(n)=\sum_{i=1}^{n}z_2(i)$$ then the contribution of these $2\left[\frac{n}3\right]$ terms to the sum is: $$Z_2\left(\left[\frac{n}3\right]\right)+2\left[\frac{n}3\right]$$
- Next, consider representations starting with "13". Choose $b_1$ to be such that $5\cdot 2^{b_1-1}\leq n\leq 4\cdot 2^{b_1}-3$, which would be the place value of the $1$ in the largest such representation less than or equal to $n$. Notice that if the $1$ is in a lower place value, but the string still began "13", then the representation would still be lesser than $n$, since it would be bounded above by $2\cdot 2^{b_1}< 5\cdot 2^{b_1-1} \leq n$. Therefore, if we take an binary number less than $\frac{n-2^{b_1}}{3}$, converted all the 1s to 3s and prepended a "1", we would get a valid representation starting with "3". The contribution of these terms to the sum would be: $$Z_2\left(\left[\frac{n-2^{b_1}}3\right]\right)+3\left[\frac{n-2^{b_1}}3\right]$$ It is possible that no suitable $b_1$ exists, in which case choose $b_1$ to be the largest value such that $4\cdot 2^{b_1}-3<n$, meaning that any number with the $1$ in the place with value $2^{b_1}$ works, giving a contribution of $2^{b_1-1}-1$ terms as: $$Z_2\left(2^{b_1-1}-1\right)+3\cdot 2^{b_1-1}-3$$
Now, consider representations starting with "100". Choose $b_2$ to be such that $$2^{b_2}\leq n \leq 7\cdot 2^{b_2-2}-3.$$ The contribution of these terms will be $$Z_2\left(\left[\frac{n-2^{b_2-1}}3\right]\right)+7\left[\frac{n-2^{b_2-1}}3\right]$$ or, if no such $b_2$ exists, letting $b_2$ instead be the greatest value such that $2^{b_2}\leq n$, giving a contribution of: $$Z_2\left(2^{b_2-2}-1\right)+7\cdot 2^{b_2-2}-7$$
Finally, we consider representation starting with "103". Choose $b_3$ to be such that $7\cdot 2^{b_3-2}\leq n \leq 5\cdot 2^{b_3-1}-3$. The contribution of thse terms will be $$Z_2\left(\left[\frac{n-2^{b_3}}3\right]\right)+6\left[\frac{n-2^{b_3}}3\right]$$ and if no such $b_3$ exists, choose the largest such that $7\cdot 2^{b_3-2}<n$. Then, the contribution will be: $$Z_2\left(2^{b_3-2}-1\right)+6\cdot 2^{b_3-2}-1.$$
We have not yet counted the strings "10", and "1". They contribute $9$ to the sum (assuming $n>2$).
Now, if you just sum up all those contributions, making the big assumption that I didn't make a single computation error in this entire post, you should get $a(2n)$. It's not really worth compiling those into a single equation, since there are essentially $8$ cases. I'll leave the odd cases to you, but it should proceed analogously. You just need to compute $Z_2(n)$ quickly, but I think this is probably easy enough since it has the identity: $$Z_2(2^{k}-1)=k\cdot (2^{k-1}-1)$$ and should have nice identities for $Z_2(2^{k_1}+2^{k_2}-1)$ and so on as we specify more digits. (There's still substantial computation to do here, but it should take linear time in the number of digits, rather than quadratic time, as the naive algorithm would take)
Solution 2:
This isn't a full answer, but might make a solution more tractable.
Define $S(n) = a(n+2) - a(n)$. (FYI I wasn't able to find $S(n)$ sequence in OEIS either)
Then, we get that
$S(2n) = a(2n+2) - a(2n) = a(n+2) + a(n+1) + (n+1) - a(n+1) - a(n) - n = a(n+2) - a(n) + 1 = S(n) + 1$
and
$S(2n+1) = a(2n+3) - a(2n+1) = a(n+1) + a(n) + 1 - a(n) - a(n-1) - 1 = a(n+1) - a(n-1) = S(n-1)$
So the recurrence for $S(2n) = S(n) + 1$ and $S(2n+1) = S(n-1)$. This still has a parity difference in the recursion, but is a bit simpler.
I spent a little while trying to work out a Josephus problem type solution for $S(n)$, with only partial results (i.e. if $n = 2^k + 3(2^j-1)$ with $0 \leq j < k$ and $2 \leq k$, then $S(n) = k - j + 4$). At the very least that shows that the differences between $a(n+2)$ and $a(n)$ vary between small constant values and up values around $\log n$.