# How to make my iterated function calculate more quickly?

Sn[n_] := x /; 0 <= n <= 8
Sn[n_] := 0 /; n > 8

Tn[n_] := 1 /; 0 <= n <= 8
Tn[n_] := 0 /; n > 8

Un[n_] := x /; 0 <= n <= 8
Un[n_] := 0 /; n > 8

Z[n_] := n^2 + n;

an[0] = 1;

an[n_] :=
an[n] = -1/
Z[n] Sum[((k)*(k - 1)*Sn[n - k] + (k)*Tn[n - k] + Un[n - k])*
an[k], {k, 0, n - 1, 1}];
an[500]


Some friends say my last code was not clear,I am very sorry.Here I rewrite the code. This code calcute too slowly,please help me!Thank you!

Using your definitions and looking at the output of an[10], we see that already here the output is very complicated, containing many nested parentheses. But an[n] is a polynomial of degree n in x so it should only have n terms (no zeroth order term here).

Much more importantly for speed, your summand is zero whenever n-k > 8. So we can restrict the sum to Max[n - 8, 0] <= k <= n -1 and replace the values of Sn, Tn, Un. That should let us Expand each an such that we don't accumulate extremely many terms/factors. We get:

an[n_] :=
an[n] = Expand[-1/
Z[n] Sum[((k)*(k - 1)*x + (k)*1 + x)*an[k], {k, Max[n - 8, 0],
n - 1, 1}]];


Now

AbsoluteTiming[an[500];]


gives

{9.699283, Null}

on my desktop computer.