I'm unhappy with it, the formal one is better

1 files changed, 192 insertions, 0 deletions

diff --git a/tutorial_1.typ b/tutorial_1.typ
new file mode 100644
index 0000000..c2989e2
--- /dev/null
+++ b/tutorial_1.typ
@@ -0,0 +1,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)
+$