Solving recurrence relation of the form $(a_{2n} = f(n), a_{2n+1} = g(n))$

Question

I have come across this problem, which has apparently been posted as a problem in the national university entrance exam in South Korea this year.

Consider the following relations:

• $a_{2n} = a_{n} - 1$
• $a_{2n+1} = 2a_{n} +1$

Find the value of $\quad\displaystyle\sum_{n=1}^{63} a_n\quad $ if $a_{20} = 1$.

Now the problem itself is straightforward. There is a simple recurrence relation for the sum that you find after rewriting the sum into sum of even-index entries and odd-index entries ($\sum_{n=1}^{2^n-1} a_n = a_1 + 3\sum_{n=1}^{2^{n-1}-1} a_n$). I find that the sum in the problem is equivalent to $364 a_1$. But I had to brute-force to find $a_1 =2 $ from the condition $a_{20} = 1$, using the two original recurrence relations.

I would like to know the general expression for $a_n$, and I am having trouble with this. One thing that I tried is I derive the recurrence relation $a_{2n+1} = 2 a_{2n} +3$ which looks like a homogeneous recurrence relation, but extrapolating the solution from that for $a_n$ will give me inconsistent results and I don't understand why.

I actually don't know much about discrete mathematics other than my brief encounter with generating functions from physics so please let me know if I am missing some basic methods.

Answer 1

I do not believe you are missing anything that could be described as basic. Indeed, I think your solution is very good.

First, with regard to your 'inconsistent' results. I suspect that the issue here is that the recurrence relation $a_{2n+1}=2a_{2n}+3$ does not tell us what $a_{2n}$ is in terms of $a_{2n-1}$. Of course, this problem is designed to be more tricky than would be the case for $a_{n+1}=2a_{n}+3$.

Secondly, can one get a general formula? The answer is yes but the formula will not be a simple one.

Essentially the form of the solution depends on the structure of $n$ as a binary number. For example:-

For $n=2^k, k\ge 0$. Then $a_n=2-k$.

For $n=2^k+1, k\ge 1$. Then $a_n=7-2k$.

For $n=2^k+2, k\ge 2$. Then $a_n=8-2k$.

For $n=2^k+3, k\ge 2$. Then $a_n=19-4k$.

...

...

I'm sure you could, with some effort, put these into a general form. However, are you interested in what will not be an especially neat solution?