# 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 '18 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? – maple May 26 '18 at 4:02
• Solve it analytically or numerically? – Αλέξανδρος Ζεγγ May 26 '18 at 4:26
• @ΑλέξανδροςΖεγγ ,I hope I can get an analytically expression. – maple May 26 '18 at 4:28
• Your defining equation is inconsistent with the initial condition for n=1: t[1]==Sum[2 t[i],{i,1,0}]. – yarchik May 27 '18 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[1] }}
*)


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

DifferenceDelta[#, n]& /@ (T[n] == Sum[2 T[i], {i, 1, n - 1}])
RSolve[{ %, T[1]==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] = 1;
T[n_Integer?Positive] := T[n] = Sum[2*T[i], {i, 1, n - 1}];


Generate a sequence from the recursion

seq = T /@ Range[10]

(* {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[100]) == (f /@ Range[100])

(* True *)


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

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

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


Checking,

(T /@ Range[100]) == (f /@ Range[100]) == (T2 /@ Range[100])

(* True *)

• Why you obtain the right solution, the pedagogical value of your answer is low, as it teaches guessing not solving... – yarchik May 27 '18 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*"]) – Bob Hanlon May 27 '18 at 12:33

Using @ubdqn's observations with RSolve:

RSolve[{t[n] == 3 t[n - 1], t[2] == 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. – yarchik May 27 '18 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] ==1 is given as part of the problem description). – kglr May 27 '18 at 4:35
• That is true, the initial condition t[1]==1 is inconsistent with t[1]=Sum[2 t[i],{i,1,0}] and therefore needs to be put by hand. – yarchik May 27 '18 at 5:05