Finding a sequence with RecurrenceTable

Question

I would appreciate if somebody could help me with the following problem:

Q: How can the following recursion equations be solved using RecurrenceTable?

$\qquad a_{2n}=2\,a_n-1,\, a_{2\,n+1}=2\,a_n+1,\, a_{1}=1$

RecurrenceTable[{a[2 n] == 2 a[n] - 1 , a[2 n + 1] == 2 a[n] + 1, a[1] == 1}, a, {n, 1, 15, 1}]

But...

Answer 1

I don't think the built-in function RecurrenceTable can handle the kind of recurrence you present in this question. However, the problem is amenable to the approach I discussed in your previous question.

First, observe that the recurrence relation is really a matter of odd and even numbrs; i.e., it is defined one way for odd numbers and only slightly differently for even ones.

Second, write a recursive function based on this observation. Like so:

Clear[a]
a[1] = 1;
a[n_?EvenQ] := 2 a[n/2] - 1
a[n_?OddQ] := 2 a[Floor[n/2]] + 1

Now, it is possible to generate a sequence to any specified length, say 63.

Table[a[i], {i, 63}]

{1, 
 1, 3, 
 1, 3, 5, 7, 
 1, 3, 5, 7, 9, 11, 13, 15, 
 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 
 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 
    33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63}