How to find a list of values of recurrence equation?

Question

I tried with RSolve,but it fails:

RSolve[{x[n + 1] == n + Sum[j*x[j], {j, 1, n}], x[1] == 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] == 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.

Answer 1

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

x /@ Range[10]

{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] == 2}, x[n], n][[1]]
    // FullSimplify[#, n > 0 && n \[Element] Integers] &

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

as per Daniel's answer.

Answer 2

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]==2 as the initial value.

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

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

Check:

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

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

Answer 3

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[1] == 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.