# Finding a sequence with RecurrenceTable

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}, a, {n, 1, 15, 1}]


But...

• You should attempt to explain your issue if possible, rather than leave people to guess what the "But.." refers to. In the documentation for RecurrenceTable it says that the equations must be in the form of a[n + i] where i is any fixed integer. Based on that, I would guess that your problem cannot be defined using RecurrenceTable. Idk if this helps, but you could define the relation like this: a = 1; a[n_] := If[EvenQ[n], 2 a[n/2] - 1, 2 a[(n - 1)/2] + 1] and that will at least get you the values for each n value. Jan 27, 2019 at 6:28
• Do you have to use the command RecurrenceTable ?
– user59583
Jan 27, 2019 at 8:57

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;
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}