# How to solve the general formula by the recursive formula in MMA?

I want to solve this problem $T(n)=\sum_{i=1}^{n-1} 2T(i),T(1)=1$, I want to know how to solve this in MMA?

## My thinking:

I have tried RSolve command, but the output is the same as the input.

$$RSolve[a[n]==\sum_{i=1}^{n-1} 2*a[i],a,n]$$

• One way to solve this in MMA is to use mathematica.stackexchange.com/questions/40/… Your sequence does show up in the oeis as oeis.org/A025192
– Bill
May 26, 2018 at 3:51
• @Bill It's an excellent site! While it seems a little bit tricky. Can I solve it with RSolve or something else? May 26, 2018 at 4:02
• Solve it analytically or numerically? May 26, 2018 at 4:26
• @ΑλέξανδροςΖεγγ ,I hope I can get an analytically expression. May 26, 2018 at 4:28
• Your defining equation is inconsistent with the initial condition for n=1: t==Sum[2 t[i],{i,1,0}]. May 27, 2018 at 5:08

"T[n] == Sum[2 T[i], {i, 1, n - 1}]" isn't really a (single) recurrence equation, so RSolve won't do much with it. (It's a different recurrence equation for each choice of $n$.) It is analogous to asking DSolve to do something useful with $f(x) = \int_{1}^{x}f(u) \,\mathrm{d}u$, which it won't because there is no derivative here. Here, we ask DSolve to solve an integral equation (or generally, an integrodifferential equation) in the same way we have asked RSolve to solve a summatory equation (or generally, a summation-recurrence equation).

Other solutions here have suggested first manipulating the equation by hand, then using RSolve. This is to convert your equation into a (single) recurrence equation. To convert the analogous integral to something DSolve will make progress with, we make Mathematica apply the fundamental theorem of calculus for us, then DSolve makes progress.

D[#,x]& /@ (f[x] == Integrate[f[u],{u,1,x}])
DSolve[%, f[x], x]
(*  f'[x] = f[x]
{{ f[x] -> E^C }}
*)


We need to do the same thing here (and we'll include T==1).

DifferenceDelta[#, n]& /@ (T[n] == Sum[2 T[i], {i, 1, n - 1}])
RSolve[{ %, T==1}, T[n], n]
(*  -T[n] + T[1 + n] == 2 T[n]
{{ T[n] -> 3^(-1+n) }}
*)


This can also be seen as $T(n+1)-T(n)=2 T(n)\iff T(n+1)=3 T(n)$ for $n>1$, so$T(n)= 3T(n-1)=9 T(n-2)=...=3^{n-2}T(2)$ and $T(2)=2$. Therefore, $T(1)=1,T(n)=2\cdot 3^{n-2}, for \quad n>1$

It is easy to deal with this problem in the numerical way. Besides the approach involved with memoization as Bob Hanlon used, another is to use Nest:

Nest[Append[#, 2 Total[#]] &, {1}, 10]
FindSequenceFunction[%[[2 ;;]], n]


generate

{1, 2, 6, 18, 54, 162, 486, 1458, 4374, 13122, 39366}

2 3^(-1 + n)


This means that $T(n) = 2\times 3^{n-2}$ for $n = 2,3,4,...$.

Clear[T];
T = 1;
T[n_Integer?Positive] := T[n] = Sum[2*T[i], {i, 1, n - 1}];


Generate a sequence from the recursion

seq = T /@ Range

(* {1, 2, 6, 18, 54, 162, 486, 1458, 4374, 13122} *)


Use FindSequenceFunction to find the general formula

f[n_] = FindSequenceFunction[seq, n] The general formula is expressed as a DifferenceRoot

Verifying that the recursion and the general formula are equivalent even for values outside the original sequence:

(T /@ Range) == (f /@ Range)

(* True *)


EDIT: As pointed out by Αλέξανδρος Ζεγγ for n > 1

Clear[T2];
T2 = 1;
T2[n_Integer?Positive] = FindSequenceFunction[{#, T[#]} & /@ Range[2, 10], n]

(* 2 3^(-2 + n) *)


Checking,

(T /@ Range) == (f /@ Range) == (T2 /@ Range)

(* True *)

• Why you obtain the right solution, the pedagogical value of your answer is low, as it teaches guessing not solving... May 27, 2018 at 4:25
• @yarchik - Presumably, a pedagogical purposes of this forum is to teach/learn the capabilities of Mathematica. Even when rigor is desired or required, guessing can provide insight and a useful first step (e.g., proof by induction). WRI has spent considerable resources on such methods. See also: FindDistribution, FindFormula, FindGeneratingFunction, FindLinearRecurrence, RootApproximant, et al. (Names["Find*"]) May 27, 2018 at 12:33

Using @ubdqn's observations with RSolve:

RSolve[{t[n] == 3 t[n - 1], t == 2}, t[n], n]


{{t[n] -> 2 3^(-2 + n)}}

• I think among of all answers, your solution approaches the problem in a very systematic way that can be recommended in many cases. First, problem is manually simplified (@ubpdqn) using mathematical intuition and only then MA is used to work out the details. May 27, 2018 at 4:20
• @yarchik, thank you. Without some pre-analysis I don't see a way to come up with the correct initial condition (especially t ==1 is given as part of the problem description).
– kglr
May 27, 2018 at 4:35
• That is true, the initial condition t==1 is inconsistent with t=Sum[2 t[i],{i,1,0}] and therefore needs to be put by hand. May 27, 2018 at 5:05