1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
|
#set document(
title: [Tutorial 1],
author: "Gidon Rosalki",
date: auto,
)
#set heading(numbering: "1.")
#set text(font: "New Computer Modern")
#set page(margin: (
bottom: 0.5cm,
right: 1.5cm,
left: 1.5cm,
top: 1.5cm,
))
#set list(indent: 10pt)
#set enum(indent: 10pt)
#show title: set align(center)
#show link: set text(rgb("005eff"))
#show link: underline
#show math.equation.where(block: true): set block(breakable: true)
#title()
#align(center)[
Gidon Rosalki \
2026-10-14
]
#let colourmaths(x, color) = text(fill: color)[$#x$]
// author: eric1102 - https://sitandr.github.io/typst-examples-book/book/typstonomicon/math_display.html
// may slightly interfere with maths blocks
#show math.equation: it => {
if it.body.fields().at("size", default: none) != "display" {
return math.display(it)
}
it
}
= Linear Recurrence
*Definition* (Linear Recurrence Relation): A *linear recurrence relation* is an equation of the form
$
X_(n + k) & = sum_(i = 0)^(k - 1) c_(i) x_(n + i)
$
Where ${c_i} subset.eq RR$, and $k in NN$ is fixed. $k$ is called "the order of the recurrence relation".
*Example* (Fibonacci):
$
x_(n + 2) & = sum_(i = 0)^(1)x_(n + i)
$
So, a solution to the recurrence relation is the sequence $overline(a) = (a_i)_(i in NN) : a_(n + k) = sum_(i = 0)^(k -
1)c_(i - 1) a_(i + n)$. \
In order for this to be defined properly, we need some initial condition. Let us say that $(a_i)_(i in NN) in RR^NN$. We
will denote by $S$ the set of all the solutions to linear recurrence relations. Then, $S$ is a vector field. As is
required by a vector field:
+ $0 in S$
+ Closed under addition: If we suppose the two series $(a_i)_(i in NN), (b_i)_(i in NN)$, and we define $ ((a) + (b))_n =
a_n + b_n $ So, to check if $a + b in S$:
$
a_(n + k) & = sum_(i = 0)^(k - 1) c_i a_(n + i) \
b_(n + k) & = sum_(i = 0)^(k - 1) c'_i a_(n + i) \
a_(n + k) + b_(n + k) & = sum_(i = 0)^(k - 1) c_i (a_(n + i) + b_(n + i))
$
As required.
+ Closed to scalar multiplication: $lambda in RR, a in S, lambda a in S$: Trivial.
Since we have a vector field, it is natural to ask questions about its dimension. Let us define
$
pi & : S -> RR^k \
pi ((a_i)_(i in NN)) & := (a_1, dots, a_k)^T
$
We will claim that $pi$ is a linear isomorphism. In order to check this:
+ We need to check that it maintains linearity:
$
pi (alpha a + beta b) & = (alpha a_1 + beta_b_1, dots, alpha a_k + beta b_k) \
$
As required.
+ Is it a one-to-one function:
$
a != b & ==> pi (a) = pi (b)? \
$
No. Let us assume by contradiction that $exists a != b : pi (a) = pi (b)$. Therefore there exists some minimum $m$ for
which $a_m != b_m$, and therefore so to they will be different after applying $pi$
+ "into": $forall r in RR^k$, we want some $s_r in S$ for which $pi (s_r) = r$.
This is equivalent to asking given a
function $f: RR -> RR$, and $f (x) = 2 x$ if it is true that $f (RR) = RR$, i.e. $forall r in RR exists w : r = 2 w$.
This is fairly trivial, since the first $k$ elements may be arbitrary, and are not restricted to anything. We are
defining that $a_(n + k)$ is based off the sum of the earlier elements.
In order for a linear isomorphism to exist between two spaces, they must have the same dimension. This means that the
space with infinite sequences $S$ has a relatively small dimension. \
Additionally, since it's one to one, we have infinite solutions. We can now reconstruct the basis of this. If we take
${e_i}_(i = 1)^(k)$ to be the standard basis of $RR^k$, then the collection ${pi^(-1) (e_i)}$ is the basis of $S$.
= Matrix form
Recall that $x_(n + k) = sum_(i = 0)^(k - 1) c_i x_(n + i)$. We may also write this in the form of a matrix:
$
A & = mat(
0, 1, 0, 0, dots, 0;
0, 0, 1, 0, dots, 0;
0, 0, 0, 1, dots, 0;
dots.v, dots.v, dots.v, dots.v, dots.down, dots.v;
c_0, c_1, c_2, dots, c_(k - 1)
) \
X_n & = (x_n, x_(n + 1), dots, x_(n + k - 1)) \
A X_n & = (x_(n + 1), x_(n + 2), dots, x_(n + n - 1), underbrace(sum_(i = 0)^(k - 1)c_i x_(n + i), x_(n + k))) \
==> X_(n + 1) & = A X_n \
==> X_(n + 2) & = A X_(n + 1) \
& = A A X_(n) \
& = A^2 X_n \
==> X_n & = A^n X_0
$
Let us assume that $A$ is diagonalisable: $exists P, D in M_k (RR)$, s.t. $D$ is diagonal, then $A = P D P^(-1)$. So,
$
x_(n + l) = A^l x_n = A^(l + n) x_0 = P D^(l + n) P^(-1) x_0
$
This neat feature means that the $n$-th power of a $k times k$ diagonalisable matrix may be computed in $O(k^3 log n)$.
= Characteristic Polynomial
*Definition* (Characteristic Polynomial): The characteristic polynomial of matrix $A$ $P_A (x) = det(X I - A)$. If
$lambda$ is a root of $P_A (X)$, then $lambda$ is an eigenvalue of $A$.
Note that eigenvalues are useful, since if $A$ is diagonalisable, then $D$ will be a diagonal matrix, where the
eigenvalues are the main diagonal.
*Claim*: The characteristic polynomial of $A$ is
$
p(x) = x^k - sum_(i = 0)^(k - 1) c_i x^i
$
_Proof_: We will prove by induction. When $k = 2$, then $det(x I - A) = det mat(x, -1; -c_0, x - c_1) = x^2 - c_1 x -
c_0$. Let us now assume that $k > 2$. We will use the Laplace expansion on the first column:
$
det(x I - A) & = det mat(
x, -1, 0, dots, 0;
0, x, -1, dots, 0;
dots.v, dots.v, dots.down, dots.v;
0, 0, 0, dots, -1;
-c_0, -c_1, -c_2, dots, x - c_(k - 1);
) \
& = x det mat(
x, -1, dots, 0;
dots.v, dots.v, dots.down, dots.v;
0, 0, dots, -1;
-c_1, -c_2, dots, x - c_(k - 1);
) + (-1)^(k) c_0 det mat(
-1, 0, dots, 0, 0;
x, -1, dots, 0, 0;
dots.v, dots.v, dots.down, dots.v, dots.v;
0, 0, dots, x, -1;
) \
& = x (x^(k - 1) - sum_(i = 1)^(k - 1)c_i x^(i - 1)) + (-1)^(k) c_0 (-1)^(k - 1) \
& = x^(k) - sum_(i = 0)^(k - 1)c_i x^(i)
$
*Claim*: If $lambda$ is an eigenvalue of $p(x)$, then:
+ $v_lambda = (1, lambda, lambda^2, lambda^3, dots, lambda^(k - 1))^T$ is the corresponding eigenvector
+ $overline(lambda) = (lambda^i)_(i = 0)^(infinity)$ is in $S$, as a solution to the recurrence relation $x_(n + k) =
sum_(i = 0)^(k - 1)c_i x_(n + i)$
+ $overline(lambda) = pi^(-1) (v_lambda)$, where $pi$ is the isomorphism from above
_Proof_: For 1, let us consider the vector $A v_lambda$. For $1 <= i <= k - 1$, the $i$-th entry of $A v_lambda$ is:
$
(A v_lambda)_i = lambda^(i) = lambda (v_lambda)_i
$
For $i = k$, since $lambda$ is a root, $0 = p (lambda) = lambda^(k) - sum_(i = 0)^(k - 1)c_i lambda^(i)$, and
$
(A v_lambda)_k = sum_(i = 0)^(k - 1) c_i lambda^(i) = lambda^(k) = lambda (v_lambda)_k
$
Therefore, $A v_lambda = lambda v_lambda$ as required. \
For 2, note that for $n >= k$:
$
lambda^(n) & = lambda^(n - k) lambda^(k) \
& = lambda^(n - k) (sum_(i = 0)^(k - 1)c_i lambda^(i)) \
& = sum_(i = 0)^(k - 1)c_i lambda^(n - k + i)
$
showing that $overline(lambda)$ is a solution. The third claim follows form the definition of $pi$.
== Returning to Fibonacci
Since we have a basis to $S$, we may conclude that given the eigenvalues, we may create a general formula for any value
$n$. For example, Fibonacci:
$
A & = mat(0, 1; 1, 1) \
p(x) & = x^2 - x - 1 \
=> phi = (1 + sqrt(5)) / 2
wide & and quad -phi^(-1) = (1 - sqrt(5)) / 2
$
Given $0, 1$ as the initial condition, then the $n$-th element is given by:
$
F_n = (phi^n - (-phi)^n) / sqrt(5)
$
|
