Difference between revisions of "Linear recurrence"
(Created page with 'A sequence <math>\{a_{0},a_{1},a_{2},\ldots\}</math> is said to obey a '''linear recurrence of order <math>k</math>''' if there exist constants <math>c_{0},c_{1},\ldots,c_{k-1}</…') |
m |
||
| Line 1: | Line 1: | ||
A sequence <math>\{a_{0},a_{1},a_{2},\ldots\}</math> is said to obey a '''linear recurrence of order <math>k</math>''' if there exist constants <math>c_{0},c_{1},\ldots,c_{k-1}</math> such that <cmath>a_{n+k} = \sum_{i=0}^{k-1}c_{i}a_{n+i}</cmath> for all <math>n \ge 0</math>. | A sequence <math>\{a_{0},a_{1},a_{2},\ldots\}</math> is said to obey a '''linear recurrence of order <math>k</math>''' if there exist constants <math>c_{0},c_{1},\ldots,c_{k-1}</math> such that <cmath>a_{n+k} = \sum_{i=0}^{k-1}c_{i}a_{n+i}</cmath> for all <math>n \ge 0</math>. | ||
| + | |||
| + | There is a systematic way of solving linear recurrences, found in the page [[Characteristic Equation]]. | ||
{{stub}} | {{stub}} | ||
[[Category:Combinatorics]] | [[Category:Combinatorics]] | ||
Latest revision as of 21:14, 28 May 2025
A sequence 
is said to obey a linear recurrence of order 
if there exist constants 
such that ![\[a_{n+k} = \sum_{i=0}^{k-1}c_{i}a_{n+i}\]](http://latex.artofproblemsolving.com/6/1/c/61cc4c8799017be3f17608de04c3da6bc37468ca.png)
for all 
.
There is a systematic way of solving linear recurrences, found in the page Characteristic Equation.
This article is a stub. Help us out by expanding it.
