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

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]

-

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]


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}

-
Warning : in Mathematica 8 and later Solve[1/2 n (1 + n) == k, n, Integers] yields the result in terms of ConditionalExpression. You should rather use simply Solve[1/2 n (1 + n) == k, n]. +1. – Artes Jan 31 '13 at 13:15
@Artes Thanks for the correction. – Mr.Wizard Jan 31 '13 at 13:17