From cbc7088a3782d83e22f638786bc539d4e3a3a47e Mon Sep 17 00:00:00 2001 From: 8oldr <8oldr@proton.me> Date: Thu, 15 Oct 2026 21:29:31 +0300 Subject: I'm unhappy with it, the formal one is better --- tutorial_1.typ | 192 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 192 insertions(+) create mode 100644 tutorial_1.typ (limited to 'tutorial_1.typ') 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) +$ -- cgit