How many recurrence relations are possible for a sequence? Example: $$ 5, 11, 29, 83, 245, \ldots $$ We have two recurrence relation:
$T_n = 3T_{n-1} - 4$
$T_n = T_{n-1} + 6 \cdot 3^{n-1}$
Both give $T_n = 3^n + 2$
Asked
Active
Viewed 102 times
1
user103828
- 2,368
-
One can note that $T_n=3^n+2$ does not solve 2. – Did Mar 17 '15 at 08:30
-
Sorry? Plugging $T_{n-1}=3^{n-1}+2$ in the RHS of 2. and checking that the result is not always $3^n+2$, what else? – Did Mar 18 '15 at 11:37
1 Answers
1
Let $s$ be an arbitrary number. Then the recurrence $$T_n=s\left(3T_{n-1}-4\right)+(1-s)\left( T_{n-1}+6\cdot 3^{n-1} \right)$$ gives the same sequence for any $s$.
user103828
- 2,368
André Nicolas
- 507,029
-
So which recurrence amongst this is correct? And what if s<=0 ? – Nandini Singhal Nov 14 '14 at 05:14
-
Also how many recurrence relations are possible for a given sequence? – Nandini Singhal Nov 14 '14 at 05:15
-
All are correct, $s$ can be anything. So there are infinitely many. The interesting thing would be to put restrictions on the type of recurrence. Or perhaps even though there are infinitely many they are in some sense finitely generated. – André Nicolas Nov 14 '14 at 05:19