# How to find a list of values of recurrence equation?

I tried with RSolve,but it fails:

RSolve[{x[n + 1] == n + Sum[j*x[j], {j, 1, n}], x == 1}, x[n], n]


Returns unevaluated for me.

I tried with RecurrenceTable:

RecurrenceTable[{x[n + 1] == n + Sum[j*x[j], {j, 1, n}], x == 1}, x, {n, 1, 10}]


but gives error and fails again.

Are there any methods that will solve my recurrence equation (i.e, give a list of values for n=1,2,3,4,...)?

Thanks.

x := 1
x[n_] := n - 1 + Sum[j x[j], {j, 1, n - 1}]

x /@ Range


{1, 2, 7, 29, 146, 877, 6140, 49121, 442090, 4420901}

Edit

$$x(1)=1$$

$$x(n+1)=n+\sum\limits_{j=1}^n j\cdot x(j) = 1+n-1+\sum\limits_{j=1}^{n-1}j\cdot x(j)+n\cdot x(n) = 1+x(n)+n\cdot x(n) \Rightarrow$$

$$x(n+1) = 1+(n+1)\cdot x(n)$$

but then

$$x(2)=x(1+1)=1+(1+1)x(1)=1+2\cdot 1=3\neq 2$$

because in

$$1+\left[n-1+\sum\limits_{j=1}^{n-1} j\cdot x(j)\right] + n\cdot x(n)$$

for $n=1$ the term in square brackets becomes

$$1-1+\sum\limits_{j=1}^0 j\cdot x(j)$$

which doesn't make sense.

So $x(2)$ has to be calculated from the first definition, and included in the RSolve as an initial condition:

x[n] /. RSolve[{x[n + 1] == 1 + (n + 1) x[n], x == 2}, x[n], n][]
// FullSimplify[#, n > 0 && n \[Element] Integers] &


-((3 n!)/2) + E Gamma[1 + n, 1]

• A few minutes ago I was able to solve it. I just waited to confirm my calculations. Thanks. May 6, 2018 at 8:59
• @corey979 Can one not do it using RSolve? May 6, 2018 at 10:11
• @corey979 Yeah I had also arrived at the same conclusion. Incidentally, the docs say that: "RSolve can solve linear recurrence equations of any order with constant coefficients. It can also solve many linear equations up to second order with nonconstant coefficients, as well as many nonlinear equations". It should have, in principle, been able to solve it straight from the sum form. May 6, 2018 at 16:55

The recurrence can be solved by noting that x[n+1]-x[n] can be expressed in terms of n and x[n]. To make this work I had to use x==2 as the initial value.

rsol =
RSolveValue[{x[n + 1] == 1 + (n + 1)*x[n], x == 2}, x[n], n]

(* Out= 1/2 (-3 Gamma[1 + n] + 2 E Gamma[1 + n, 1]) *)


Check:

Table[rsol, {n, 2, 10}]

(* Out= {2, 7, 29, 146, 877, 6140, 49121, 442090, 4420901} *)

• Thanks for alternative soluton. :) May 6, 2018 at 13:29
• I just realized this can be solved exactly this way, with x == 2 as an initial condition; x == 1 leads to x = 3, so other terms are also off. May 6, 2018 at 15:50

I am not able to code it up right now. But here is an idea of how one can possibly use RSolve/RSolveValue to find the solution to the recurrence equation without manually simplifying first.

From the examples, it seems that RSolve works for recurrence relations where the no. of unknowns is fixed. If that's the case one can cast the recurrence equation at hand into one with fixed no of unknowns albeit with variable coefficients(which Mathematica can handle).

So, a pseudo-code would be:

Clear["Global*"];
l[n_, max_] := Join[Range[n], ConstantArray[0, max - n]];
rec[max_, n_] := {x[n + 1] == n + l[n, max].Table[x[i], {i, 1, max}],
x == 0};
RSolveValue[rec[10, n], x[n], n]


Above, l denotes the variable coefficient of x[j]'s on the RHS, which are taken to zero after its index j. The above pseudo-code should give correct results for the unknowns upto x[max]` with $max=10$.

Note that, the above code doesn't work. I have to fix a lot of things. But I wanted to get the idea across so that someone can quickly code it up.