#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)
$