{%hackmd @YuRen-tw/article-theme %}

# Horadam Sequences

> 礙於技術限制，各項公式未能個別標註出處。
> 參考文獻統一排列於「[Reference](#Reference)」節。
> 學術引用時務必完整標示所有文獻。

<div class="invisible-box">

$\newcommand{\args}[1]{\langle{#1}\rangle}$
$\newcommand{\Hrd}[2][w]{\mathbf{#1}\args{#2}}$
$\newcommand{\LcsI}[1]{\Hrd[u]{#1}}$
$\newcommand{\LcsII}[1]{\Hrd[v]{#1}}$
$\newcommand{\Mat}[1]{\begin{bmatrix} #1 \end{bmatrix}}$
$\newcommand{\HProd}[2]{\Mat{ #1 \\ #2 }}$
$\newcommand{\HProdS}[3]{#3 \otimes\hspace{-.89em}\HProd{#1}{#2}}$
</div>

> :::spoiler Table of Contents
> [TOC]
> :::

## Introduction
### Horadam sequences and Lucas sequences

<div class="definition" data-info="Horadam sequence">

For any $a$, $b$, $p$, and $q$, a Horadam sequence is $\Hrd{a,b;p,q} = (w_n)_{n=0}^\infty$, where $(w_n)$ satisfies the following second-order linear homogeneous recurrence relation:
\begin{align*}
w_0 &= a,\quad w_1 = b,\\
w_n &= p w_{n-1} - q w_{n-2}.
\end{align*}

We can also write
\\[
\Mat{w_n \\ w_{n+1}}
= \Mat{0 & 1 \\ -q & p}^n \Mat{a \\ b}.
\\]
</div>

A Haradam sequences is trivial if $p = 0$ or $q = 0$.
From now on, we suppose that $p, q \ne 0$.
- If $p = 0$, then $w_{2n} = (-q)^na$ and $w_{2n+1} = (-q)^nb$.
- If $q = 0$, then $w_n = p^{n-1}a$.

<div class="example">

First few terms of $(w_n)$: $a$, $b$, $pb-qa$, $(p^2-q)b-pqa$, $(p^3-2pq)b-(p^2-q)qa$, $(p^4-3p^2q+q^2)b-(p^3-2pq)qa$.

| $n$ | | $w_n$ |
|:---:|:---|:---|
| $0$ | $1$ | $a$ |
| $1$ | $1$ | $b$
| $2$ | $p,q$ | $b,-a$ |
| $3$ | $p^2,pq,q$ | $b,-a,-b$ |
| $4$ | $p^3,p^2q,pq,q^2$ | $b,-a,-2b,a$ |
| $5$ | $p^4,p^3q,p^2q,pq^2,q^2$ | $b,-a,-3b,2a,b$ |
| $6$ | $p^5,p^4q,p^3q,p^2q^2,pq^2,q^3$ | $b,-a,-4b,3a,3b,-a$ |
</div>

<div class="definition" data-info="Lucas sequence">

For any $p$ and $q$, Lucas sequences of the first kind and the second kind are, respectively,
\\[
\LcsI{p, q} = \Hrd{0, 1; p, q},\quad
\LcsII{p, q} = \Hrd{2, p; p, q}.
\\]
</div>

In the rest of this article, we use $w_n$, $u_n$, and $v_n$ to denote those sequences.
If necessary, we write $w_n\args{a,b;p,q}$, $u_n\args{p,q}$, and $v_n\args{p,q}$ to avoid ambiguity.

<div class="example">

First few terms of the sequences:

| $n$ | $u_n$ | $v_n$ |
|:---:|:---|:---|
| $0$ | $0$ | $2$ |
| $1$ | $1$ | $p$ |
| $2$ | $p$ | $p^2-2q$ |
| $3$ | $p^2-q$ | $p^3-3pq$ |
| $4$ | $p^3-2pq$ | $p^4-4p^2q+2q^2$ |
| $5$ | $p^4-3p^2q+q^2$ | $p^5-5p^3q+5pq^2$ |
| $6$ | $p^5-4p^3q+3pq^2$ | $p^6-6p^4q+9p^2q^2-2q^3$ |
</div>

<div class="example">

| Name | Definition | OEIS |
|:---:|:---:|:---:|
| Fibonacci numbers | $\LcsI{1, -1}$ | [A000045](https://oeis.org/A000045)
| Lucas numbers | $\LcsII{1, -1}$ | [A000032](https://oeis.org/A000032)
| Pell numbers | $\LcsI{2, -1}$ | [A000129](https://oeis.org/A000129)
| Jacobsthal numbers | $\LcsI{1, -2}$ | [A001045](https://oeis.org/A001045)
| $\sqrt{\dfrac{n(n+1)}{2}}$ | $\LcsI{6, 1}$ | [A001109](https://oeis.org/A001109)
| $\displaystyle\sum_{k=0}^{n-1} x^k = \frac{x^n-1}{x-1}$ | $\LcsI{x+1, x}$ | [A002275](https://oeis.org/A002275)
| $x^n + 1$ | $\LcsII{x+1, x}$ |
| $2 \cdot T_n(x)$ | $\LcsII{2x, 1}$ |
| $U_{n-1}(x)$ | $\LcsI{2x, 1}$ |

> The $T_n(x)$ and $U_n(x)$ are the Chebyshev polynomials of the first kind and the second kind, respectively.
</div>

<div class="definition" data-name="Property" data-info="generating funtion">

The generating function of the sequence $(w_n)$ is
\\[
W(x)
= \frac{a + (b-pa)x}{1 - px + qx^2}.
\\]

> The generating function of a sequence $(a_n)$ is the formal power series $\sum_{n=0}^\infty a_n x^n$.
</div>

### Characteristic polynomial and closed form

If we are in some good fields like complex numbers, then we can use the closed-form expression to show some properties about a given sequence.
However, if we are in some general module, we may not have such good tools.
Fortunately, almost all of the properties about the Horadam sequences can be proved by induction :D.

<div class="definition" data-info="characteristic polynomial">

The polynomial $\lambda^2 - p\lambda + q$, which is called the characteristic polynomial of the sequence $(w_n)$, has two roots:
\\[
\alpha = \frac{p + \sqrt{d}}{2},\quad
\beta = \frac{p - \sqrt{d}}{2},
\\]
where $d = p^2 - 4q$.

Note that $\alpha = \beta$ iff $d = 0$.
If so, we call it the degenerate case.
</div>

Certainly we have $\alpha+\beta = p$, $\alpha\beta = q$, and $\alpha-\beta = \sqrt{d}$.

<div class="definition" data-name="Property" data-info="closed form">

Let $A = \dfrac{b - a\beta}{\alpha - \beta}$ and $B = \dfrac{a\alpha - b}{\alpha - \beta}$ for $d \ne 0$.
Then we have
| | $d \ne 0$ | $d = 0$ |
|:---:|:---:|:---:|
| $w_n$ | $A\alpha^n + B\beta^n$ | $bn\alpha^{n-1}-a(n-1)\alpha^n$ |
| $u_n$ | $\dfrac{\alpha^n - \beta^n}{\alpha - \beta}$ | $n\alpha^{n-1}$ |
| $v_n$ | $\alpha^n + \beta^n$ | $2\alpha^n$ |

> Also, we have $AB = e/d$, where $e = pab - qa^2 - b^2 = w_0w_2 - w_1^2$.
</div>

In any world having the mathematical induction, there is a induction that can apply to Horadam sequences.

<div class="remark unnumbered" data-info="induction">

Let $P(n)$ be a statement involving $n \in\mathbb{N}$.
Then $P(n)$ holds for any $n \ge n_0$ if it satisfies the following:
1. Both the cases $P(n_0)$ and $P(n_0+1)$ hold;
2. The case $P(k+2)$ hold whenever both the cases $P(k)$ and $P(k+1)$ hold.
</div>

### Over general modules

Not only in the integers, we can define the Haradam sequences $\Hrd{a,b;p,q}$ over any left $R$-module ${}_RM$ where $p, q \in R$ and $a,b \in M$.
Also, every properties about the Horadam sequences have a corresponding *right* analog.

<div class="definition" data-info="right Horadam sequence">

A *right* Horadam sequence is $\Hrd[\hat{w}]{a,b;p,q} = (\hat{w}_n)$, where $(\hat{w}_n)$ satisfies the recurrence relation
\begin{align*}
\hat{w}_0 &= a,\quad \hat{w}_1 = b,\\
\hat{w}_n &= \hat{w}_{n-1} p - \hat{w}_{n-2} q.
\end{align*}
</div>

We write $x \sim y$ if $x$ and $y$ commute under multiplication, i.e., $xy = yx$.
Note that Lucas sequences can only be defined in $R$ and $2 = 1 + 1$.

<div class="theorem proposition">

- $p, q \sim (u_n)$ if and only if $p \sim q$.
- If $p \sim q$, then $p, q \sim (v_n)$.
- For $M = R$, if $p, q \sim (w_n)$, then $(\hat{w}_n) = (w_n)$.
</div>

## Properties
### Describe Horadam sequences by Lucas sequences

<div class="theorem proposition">

- $w_n\args{a+a',b+b'; p,q} = w_n\args{a,b;p,q} + w_n\args{a',b';p,q}$.
- $w_n\args{ac,bc; p,q} = w_n\args{a,b;p,q} \cdot c$.
- If $p, q \sim r$, then $w_n\args{ra,rb; p,q} = r \cdot w_n\args{a,b;p,q}$.
</div>
<div class="proof">

Let $(w_n) = \Hrd{a,b;p,q}$ and
$(w'_n) = \Hrd{a',b';p,q}$.
Then we have the recurrence relations
\begin{align*}
w_n + w'_n
&= pw_{n-1} - qw_{n-2} + pw'_{n-1} - qw'_{n-2}\\
&= p(w_{n-1} + w'_{n-1}) - q(w_{n-2} + w'_{n-2}),
\end{align*}
\begin{align*}
w_n c
&= (pw_{n-1} - qw_{n-2})c\\
&= p(w_{n-1} c) - q(w_{n-2} c).
\end{align*}
\begin{align*}
r w_n
&= r (pw_{n-1} - qw_{n-2})\\
&= p(r w_{n-1}) - q(r w_{n-2}).
\end{align*}
</div>

<div class="theorem">

Let $(u_n) = \LcsI{p,q}$ where $p,q \in R$, and let $a,b \in {}_RM$, then
- $w_n\args{0,b;p,q} = u_n b$.
- $w_n\args{a,b;p,q} = u_n b - u_{n-1} qa$.
</div>
<div class="proof">

Let $(w_n) = \Hrd{0,b;p,q}$.
If $w_k = u_kb$ and $w_{k+1} = u_{k+1}b$, we have
\begin{align*}
w_{k+2}
&= pw_{k+1} - qw_k\\
&= (pu_{k+1} - qu_k)b
= u_{k+2}b.
\end{align*}
Thus, since $w_0 = 0 = 0b = u_0 b$ and $w_1 = b = 1b = u_1b$, we have $w_n = u_n b$ by induction.

Moreover,
\begin{align*}
w_n\args{a,b;p,q}
&= w_n\args{0,b; p,q} + w_n\args{a,0; p,q}\\
&= w_n\args{0,b; p,q} + w_{n-1}\args{0, -qa; p,q}\\
&= u_n b - u_{n-1} qa.
\end{align*}
</div>

### Multipermutations of two objects

<div class="definition">

Let $\mathfrak{S}_2^{(m,k)}\args{p,q}$ be a collection of functions $\sigma: [m+k] \to \{p, q\}$ satisfying $|\sigma^{-1}(\{ p \})| = m$ (and $|\sigma^{-1}(\{ q \})| = k$).
> Where $[m+k] := \{1,2, \dots, m+k\}$.

Let $S(m,k) = \sum_\sigma \sigma(1)\sigma(2)\cdots \sigma(m+k)$, where $\sigma$ ranges over $\mathfrak{S}_2^{(m,k)}$.
</div>

In combinatorics, the set $\mathfrak{S}_n^{(m_1,m_2,\dots,m_n)}$ is the set of multipermutations of $n$ objects $\{ x_1, x_2, \dots, x_n \}$ such that each object $x_i$ occurs $m_i$ times in each multipermutation.
In other words, the set $\mathfrak{S}_n^{(m_1,m_2,\dots,m_n)}$ is the set of permutations of the multiset $\{ x_1^{m_1}, x_2^{m_2}, \dots, x_n^{m_n} \}$, where each $x_i$ is of multiplicity $m_i$.

<div class="theorem proposition">

- $|\mathfrak{S}_2^{(m,k)}| = \binom{m+k}{k}$.
- $S(m,k) = \begin{cases}
0 & m < 0 \text{ or } k < 0;\\
q^k & m = 0;\\
p^n & k = 0.
\end{cases}$
- $S(m,k) = pS(m-1,k) + qS(m,k-1)$.
- $S(m,k) = S(m-1,k)p + S(m,k-1)q$.
- If $p \sim q$, then $S(m,k) = \binom{m+k}{k} p^mq^k$.
</div>
<div class="example unnumbered">

If we write $\sigma(1)\sigma(2)\cdots \sigma(m+k)$ for $\sigma\in\mathfrak{S}_2^{(m,k)}$, then we have
\begin{align*}
\mathfrak{S}_2^{(3,2)} = \{\,
& p^3q^2,\ p^2qpq,\ pqp^2q,\ qp^3q,\ p^2q^2p,\\
& pqpqp,\ qp^2qp,\ pq^2p^2,\ qpqp^2, q^2p^3\,\},
\end{align*}
and $|\mathfrak{S}_2^{(3,2)}| = 10 = \binom{3+2}{2}$.
</div>

<div class="theorem">

Let $(u_n) = \LcsI{p,q}$, then we have
\\[
u_n
= \sum_{k=0}^\infty (-1)^k S(n-2k-1, k).
\\]
Moreover, if $p \sim q$, we have
\\[
u_n
= \sum_{k=0}^\infty \binom{n-k-1}{k}p^{n-2k-1}(-q)^k.
\\]
If $p$ is again a unit (i.e., is invertible), then we have
\\[
u_n
= p^{n-1}\sum_{k=0}^\infty \binom{n-k-1}{k} \Bigl(\frac{-q}{p^2}\Bigr)^k.
\\]
> The $\infty$ is only for convenience, since $S(n-2k-1, k) = 0$ if $k > (n-1)/2$.
</div>
<div class="proof">

Let $s_n = \sum_{k=0}^\infty (-1)^k S(n-2k-1, k)$.
Then we have $s_0 = 0$ and $s_1 = S(0,0) = 1$.
And we also get the recurrence relation
\begin{align*}
s_{n+2}
&= \sum_{k=0}^\infty (-1)^k S(n-2k+1, k)\\
&= \sum_{k=0}^\infty (-1)^k pS(n-2k, k) + \sum_{k=1}^\infty (-1)^k qS(n-2k+1, k-1)\\
&= \sum_{k=0}^\infty (-1)^k pS(n-2k, k) - \sum_{k=0}^\infty (-1)^k qS(n-2k-1, k)\\
&= ps_{n+1} - qs_n.
\end{align*}
Therefore $(s_n) = \LcsI{p,q} = (u_n)$ by induction.
</div>

<div class="theorem corollary">

Let $(u_n) = \LcsI{p,q}$, then we have
\\[
u_n = u_{n-1}p - u_{n-2}q.
\\]
This is to say that $\Hrd[\hat{u}]{p,q} = \LcsI{p,q}$.
</div>

<div class="theorem corollary">

If $p, q \sim r$, then we have
- $u_n\args{pr,qr^2} = r^{n-1} \cdot u_n\args{p,q}$.
- $w_n\args{a,b; pr,qr^2} = r^{n-1} \cdot w_n\args{ra,b;p,q}$.
</div>

### Product formulae

<div class="definition">

Let $\HProdS{n}{m}{r}$ denote the product $\hat{w}_n\args{a',b';p,q}\cdot r \cdot w_m\args{a,b;p,q}$, and $\HProd{n}{m} = \HProdS{n}{m}{1}$.
> The product is an element in the tensor product $M \otimes_R M$.
> The notation here is only for convenience :P.
</div>

Note that if $M=R$ and $r \sim (\hat{w}_n)$, then $\HProdS{n}{m}{r} = r \cdot \HProd{n}{m}$.

<div class="theorem" data-info="the product formula">

For any $n$, $m$, and $k$, we have
\\[
\HProd{n}{m} - \HProdS{n-1}{m-1}{q}
= \HProd{n+k}{m-k} - \HProdS{n+k-1}{m-k-1}{q}.
\\]

> I think that this is more readable instead of
> \\[
> \hat{w}_n w_m - \hat{w}_{n-1} q w_{m-1}
> = \hat{w}_{n+k} w_{m-k} - \hat{w}_{n+k-1} q w_{m-k-1}.
> \\]
</div>
<div class="proof">

We have
\begin{align*}
& \HProd{n}{m} - \HProdS{n-1}{m-1}{q}\\
&= \Bigl(\HProdS{n}{m-1}{p} - \HProdS{n}{m-2}{q}\Bigr) - \Bigl(\HProdS{n}{m-1}{p} - \HProd{n+1}{m-1}\Bigr)\\
&= \HProd{n+1}{m-1} - \HProdS{n}{m-2}{q}.
\end{align*}
Continue in this manner, then we get the result.
</div>

Similarly, if $p \sim q$, then we have
\\[
\HProdS{n}{m}{q^r} - \HProdS{n-1}{m-1}{q^{r+1}}
= \HProdS{n+k}{m-k}{q^r} - \HProdS{n+k-1}{m-k-1}{q^{r+1}}.
\\]

<div class="theorem corollary">

If $p \sim q$, then for any $n$, $m$, $k$, $r$, and $s$, we have
\\[
\HProdS{n}{m}{q^r} - \HProdS{n+k}{m-k}{q^r}
= \HProdS{n-s}{m-s}{q^{r+s}} - \HProdS{n+k-s}{m-k-s}{q^{r+s}}.
\\]
</div>

### Subsequences

<div class="theorem lemma">

If $p \sim q$, then we have $u_k v_k = u_{2k} = v_k u_k$.
</div>
<div class="proof">

Since $v_0 = 2$, $v_1 = p$, and $(u_n) = (\hat{u}_n)$, by the product formula, we have
\begin{align*}
u_k v_k - u_{k-1} q v_{k-1}
&= u_{2k-1} p - 2u_{2k-2}q\\
&= u_{2k} - u_{2k-2}q.
\end{align*}
Thus, since $p \sim q$, we have
\begin{align*}
u_k v_k - u_{2k}
&= u_{k-1} q v_{k-1} - u_{2k-2}q\\
&= q(u_{k-1}v_{k-1} - u_{2k-2}).
\end{align*}
Continue in this manner, we get $u_k v_k - u_{2k} = q^k(0-0) = 0$.
</div>

Since $p$ and $q$ are always independent in our derivations, we can actually factor out $u_k$ from $u_{2k}$ and confidently say $v_k = \dfrac{u_{2k}}{u_k}$.

<div class="theorem">

Let $(w_n) = \Hrd{a, b; p, q}$ and $(v_k) = \LcsII{p,q}$.
If $p \sim q$, then
\\[
(w_{kn+t})_{n=0}^\infty = \Hrd{w_t, w_{k+t}; v_k, q^k}.
\\]

That is to say, the subsequence of a Horadam sequence of which indices form an arithmetic progression, is again a Horadam sequence.
</div>
<div class="proof">

Let $(s_n) = (w_{kn})$.
It is sufficient to show that $(s_n) = \Hrd{w_0,w_k;v_k,q^k}$.

Let $\gamma = w_{kn+1}$ and $(u_k) = \LcsI{p,q}$, then we have
\begin{align*}
s_{n+m}
&= w_{km}\args{s_n,\gamma;p,q}\\
&= u_{km} \gamma - u_{km-1} q s_n.
\end{align*}
Thus we get $u_k \gamma = s_{n+1} + u_{k-1} q s_n$.
Then we have
\begin{align*}
u_k s_{n+2}
&= u_k (u_{2k} \gamma - u_{2k-1} q s_n)\\
&= u_{2k} (u_k \gamma - u_{k-1}qs_n) - (u_k u_{2k-1} - u_{k-1}u_{2k}) q s_n\\
&= u_{2k} s_{n+1} - (u_k u_{2k-1} - u_{k-1}u_{2k}) q s_n\\
&= u_{2k} s_{n+1} - (u_1 u_k - u_0 u_{k+1}) q^k s_n\\
&= v_k (u_k s_{n+1}) - q^k (u_k s_n),
\end{align*}
which form a recurrence relation and gives $(u_k s_n)_{n=0}^\infty = u_k \cdot \Hrd{w_0,w_k;v_k,q^k}$.

Therefore, since the $u_k$ is cancellative (why?), we get
\\[
(s_n) = \Hrd{w_0,w_k;v_k,q^k}.
\\]
</div>

<div class="theorem corollary">

If $p \sim q$, then we have
\\[
u_{kn} = w_k\args{0,u_n;v_n,q^n} = u_n \cdot u_k\args{v_n,q^n}.
\\]
</div>

<div class="example unnumbered">

If $p \sim q$, then
\\[
\frac{u_{2n}}{u_n} = u_2\args{v_n,q^n} = v_n,\quad
\frac{u_{3n}}{u_n} = u_3\args{v_n,q^n} = v_n^2 - q^n.
\\]
</div>

> ---
> *Work In Progress*...
>
> ---

## Reference
> 礙於技術限制，各項公式未能個別標註出處。
> 參考文獻按數學論文慣例，以字母順序統一排列於下。
> 學術引用時務必完整標示所有文獻。

- A. F. Horadam, Basic properties of a certain generalized sequence of numbers, *Fibonacci Quart.* **3** (1965), 161--176.
- K.-W. Chen and Y.-R. Pan, Greatest common divisors of shifted Horadam sequences, *J. Integer Seq.* **23** (2020), [Article 20.5.8](https://cs.uwaterloo.ca/journals/JIS/VOL23/Pan/pan32.html).
- P. J. Larcombe, O. D. Bagdasar, and E. J. Fennessey, Horadam sequences: a survey, *Bull. Inst. Combin. Appl.* **67** (2013), 49--72.
- P. J. Larcombe, Horadam sequences: a survey update and extension, *Bull. Inst. Combin. Appl.* **80** (2017), 99--118.