---
tags: Advanced Discrete Structure
---

{%hackmd BkVfcTxlQ %}

# Advanced Discrete Structure Note 2

## Linear Recurrence w/ Constant Coef.s

### Canonical Form of Recurrence Relation (Difference Equation)

\\[a_n+c_1a_{n-1}+\dots+c_ma_{n-m}=f(n)\\], where $c$s are all constants and $f(n)$ is a function of $n$.

> This has some things to do with _Lin. Alg._, _O.D.E_., ...

:::info
If we have a set of _general solutions_ to **homogenious system** $c_0a_n+c_1a_{n-1}+\dots+c_ma_{n-m}=0$ (null space) and a _particular solution_ to the orginal recurrence, then we could find that the _particular_ one plus any of the _general_ one would satisfy the relation, which are called the _total solutions_.
:::

### _General Solutions_ to **Homogenious System**

Characteristic Equation
: $x^n+c_1x^{n-1}+\dots+c_m=0$

Order of Linear Recurrence
: $m$
: The difference between the highest and lowest subscript of $a$
: The degree of _characteristic equation_

If $\alpha,\beta,\dots$ are roots to _characteristic equation_, then $\forall A\alpha$ and $\alpha+\beta$ ... are _general solutions_ to **homogenious system**. There are 3 cases for the root to _characteristic equation_ worthy of noting:

Distinct Real Roots $\alpha_1,\alpha_2,\dots,\alpha_m$
: It's obivous that we could have the set of _general solutions_ to **homogenious system** $a_k=\sum_{i=1}^mA_i\alpha_i^k$ satisfying _characteristic equation_, where $A_i$ are $m$ arbitrarily constants and $\alpha_i^k$ are $m$ _linear independent_ functions.

Repeated Real Roots
: If there are repeated roots, then it means that we would have some _linear dependent_ functions. So as to avoid this, we should multiply $\alpha_i^k$ by $k^0=1,k,\dots$ so that we would have $m$ _linear independent_ functions to construct _general solutions_ to **homogenious system**.

Complex Roots
: Represent the complex roots in polar coordinate $r(\cos\theta+i\sin\theta)$ and discuss the above two cases.

The $m$ constants $A_i$ could be determined uniquely by the initial $m$ terms of $a$.

### _Paritcular Solutions_

We solve the _particular solution_ $p(n)$ based on the assumption that it is similar to $f(n)$. By means of undetermined coef. method, we could construct a _particular solution_.

E.g., if $f(n)$ is a polynomial, then we suppose the $p(n)$ to be a polynomial of the same degree; if $f(n)$ is a exponential function, then we suppose the $p(n)$ to be a exponential function w/ the same base; if $f(n)$ is sum of a polynomial and a exponential function, then we suppose the $p(n)$ to be the combination.

:::warning
If there no solution to the coef. of our supposed $p(n)$ (e.g., Assignment 3 Problem 2a), then we might multiply $p(n)$ by $n$?
:::

### Solve by _[GF](/qlRxCi-ES_ujOGiJM0qiHw#Ordinary-Generating-Function-OGF)_

We could have the closed form of $a_n$ by _GF_. First we suppose the _OGF_ of $a_n$ to be $A(x)$. Then we summarize the terms in recurrence relation to $x^k$ and solve $A(x)$.

For instance, if we have a $m$-order recurrence relation $a_n+c_1a_{n-1}+\dots+c_ma_{n-m}=f(n)$, then
$$
\sum_{k=m}^\infty a_kx^k+c_1\sum_{k=m}^\infty a_{k-1}x^{k-1}+\dots+c_m\sum_{k=m}^\infty a_{k-m}x^{k-m}=\sum_{k=m}^\infty f(k)x^k\\
(A(x)-a_0-a_1x-\dots-a_{m-1}x^{m-1})+c_1x(A(x)-a_0-\dots-a_{m-2}x^{m-2})+\dots+c_mx^mA(x)=\sum_{k=m}^\infty f(k)x^k
$$
.

## Special Non-Linear Recurence (Convolution)

If $a_k=a_{k-m}a_0+a_{k-m-1}a_1+\dots+a_0a_{k-m}=\sum_{i+j=k-m}a_ia_j$, then $A(x)$ except the first $m$ terms would equal to $x^mA^2(x)$.

If $b_k=a_{k-m}b_0+a_{k-m-1}b_1+\dots+a_0b_{k-m}=\sum_{i+j=k-m}a_ib_j$, then $B(x)$ except the first $m$ terms would equal to $x^mA(x)B(x)$.

### Binary String Pattern

$m$
: Length of the pattern.

$a_n$
: \# of $n$-bit binary strings that the pattern is first detected at bit $n$.
: $a_i=0\forall i\in[0,m)$

$b_n$
: \# of $n$-bit binary strings that the pattern is detected at bit $n$.
: $b_0=1$ for the sake of convenience.
: $b_i=0\forall i\in(0,m)$

First since \\[b_k+b_{k-m+1}=2^{k-m}\\], we could solve $b$ by _GF_ or other techniques.

For $a$, we could find that $b_k=a_k+a_{k-m}b_m+a_{k-m-1}b_{m+1}+\dots+a_mb_{k-m}=\sum_{i+j=k}a_ib_j$. Thus $B(x)-1=A(x)B(x)\implies A(x)=1-\frac{1}{B(x)}$.

{%hackmd @nevikw39/signature %}