How can I get the general term of this recurrence equations?

Question

Following is the recurrence relation:

a[1] = 1;
a[n_] := a[n - a[n - 1]] + 1
Array[a, 28]

I tried to use RSolve, but it doesn't gives a correct answer.

Clear[a]
RSolve[{a[n] == a[n - a[n - 1]] + 1}, a[n], a]

Answer 1

First, I believe your RSolve syntax is incorrect. I think you want n as the last argument, and you should also have the a[1] == 1 rule:

RSolve[{a[n] == a[n - a[n - 1]] + 1, a[1] == 1}, a[n], n]

This gives a more informative (error?) message:

RSolve::nestdv: The expression a[-1+n] has nested dependent variables. >>

Apparently RSolve doesn't like that.

Second, your recursive function is very inefficient because it lacks memoization. Adding that will make it more practical:

a[1] = 1;
a[n_] := a[n] = a[n - a[n - 1]] + 1

Array[a, 500000] // Timing // First

1.529

Finally, we can work out a function for the nth term manually. Observe that in your sequence each number n repeats n times:

1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, ...

The jump points are therefore triangular numbers:

# (# + 1)/2 & ~Array~ 5

{1, 3, 6, 10, 15}

We can invert this equation with Solve:

Solve[n (n + 1)/2 == x, n]

{{n -> 1/2 (-1 - Sqrt[1 + 8 x])}, {n -> 1/2 (-1 + Sqrt[1 + 8 x])}}

Then pick the correct branch and add Ceiling:

fn[x_] := Ceiling[ (Sqrt[1 + 8 x] - 1)/2 ]

Now:

fn ~Array~ 15

{1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5}