5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$
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.

$\endgroup$
  • $\begingroup$ A few minutes ago I was able to solve it. I just waited to confirm my calculations. Thanks. $\endgroup$ – Mariusz Iwaniuk May 6 '18 at 8:59
  • $\begingroup$ @corey979 Can one not do it using RSolve? $\endgroup$ – Subho May 6 '18 at 10:11
  • $\begingroup$ @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. $\endgroup$ – Subho May 6 '18 at 16:55
5
$\begingroup$

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} *)
$\endgroup$
  • $\begingroup$ Thanks for alternative soluton. :) $\endgroup$ – Mariusz Iwaniuk May 6 '18 at 13:29
  • $\begingroup$ I just realized this can be solved exactly this way, with x[2] == 2 as an initial condition; x[1] == 1 leads to x[2] = 3, so other terms are also off. $\endgroup$ – corey979 May 6 '18 at 15:50
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.