Horadam Sequences

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

$$

$$

$$

$$

$$

$$

$$

Table of Contents

• Horadam Sequences
  • Introduction
    • Horadam sequences and Lucas sequences
    • Characteristic polynomial and closed form
    • Over general modules
  • Properties
    • Describe Horadam sequences by Lucas sequences
    • Multipermutations of two objects
    • Product formulae
    • Subsequences
  • Reference

Introduction

Horadam sequences and Lucas sequences

For any

$a$,

$b$,

$p$, and

$q$, a Horadam sequence is

$\mathbf{w}⟨a,b;p,q⟩=(w_n{)}_{n=0}^{\mathrm{\infty }}$, where

$(w_n)$ satisfies the following second-order linear homogeneous recurrence relation:

$$\begin{array}{rl}{w}_0& =a,w_1=b,\\ w_n& =p{w}_{n-1}-q{w}_{n-2}.\end{array}$$

We can also write

$$\left[\begin{array}{c}{w}_n\\ w_{n+1}\end{array}\right]={\left[\begin{array}{cc}0& 1\\ -q& p\end{array}\right]}^n\left[\begin{array}{c}a\\ b\end{array}\right].$$

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{)}^{n}a$ and
  $w_{2n+1}=(-q{)}^{n}b$.
• If
  $q=0$, then
  $w_n=p^{n-1}a$.

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^{2}q+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^{2}q,pq,q^2$	$b,-a,-2b,a$
$5$	$p^4,p^{3}q,p^{2}q,p{q}^2,q^2$	$b,-a,-3b,2a,b$
$6$	$p^5,p^{4}q,p^{3}q,p^2{q}^2,p{q}^2,q^3$	$b,-a,-4b,3a,3b,-a$

For any

$p$ and

$q$, Lucas sequences of the first kind and the second kind are, respectively,

$$\mathbf{u}⟨p,q⟩=\mathbf{w}⟨0,1;p,q⟩,\mathbf{v}⟨p,q⟩=\mathbf{w}⟨2,p;p,q⟩.$$

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⟨a,b;p,q⟩$,

$u_n⟨p,q⟩$, and

$v_n⟨p,q⟩$ to avoid ambiguity.

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^{2}q+2q^2$
$5$	$p^4-3p^{2}q+q^2$	$p^5-5p^{3}q+5p{q}^2$
$6$	$p^5-4p^{3}q+3p{q}^2$	$p^6-6p^{4}q+9p^2{q}^2-2q^3$

Name	Definition	OEIS
Fibonacci numbers	$\mathbf{u}⟨1,-1⟩$	A000045
Lucas numbers	$\mathbf{v}⟨1,-1⟩$	A000032
Pell numbers	$\mathbf{u}⟨2,-1⟩$	A000129
Jacobsthal numbers	$\mathbf{u}⟨1,-2⟩$	A001045
$\sqrt{{\displaystyle \frac{n(n+1)}{2}}}$	$\mathbf{u}⟨6,1⟩$	A001109
${\displaystyle \sum _{k=0}^{n-1}{x}^k=\frac{x^n-1}{x-1}}$	$\mathbf{u}⟨x+1,x⟩$	A002275
$x^n+1$	$\mathbf{v}⟨x+1,x⟩$
$2\cdot T_n(x)$	$\mathbf{v}⟨2x,1⟩$
$U_{n-1}(x)$	$\mathbf{u}⟨2x,1⟩$

The

$T_n(x)$ and

$U_n(x)$ are the Chebyshev polynomials of the first kind and the second kind, respectively.

The generating function of the sequence

$(w_n)$ is

$$W(x)=\frac{a+(b-pa)x}{1-px+q{x}^2}.$$

The generating function of a sequence

$(a_n)$ is the formal power series

$\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n$.

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.

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},\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.

Certainly we have

$\alpha +\beta =p$,

$\alpha \beta =q$, and

$\alpha -\beta =\sqrt{d}$.

Let

$A={\displaystyle \frac{b-a\beta }{\alpha -\beta }}$ and

$B={\displaystyle \frac{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$	${\displaystyle \frac{{\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-q{a}^2-b^2=w_0{w}_2-w_1^2$.

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

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.

Over general modules

Not only in the integers, we can define the Haradam sequences

$\mathbf{w}⟨a,b;p,q⟩$ over any left

$R$-module

${}_{R}M$ where

$p,q\in R$ and

$a,b\in M$.
Also, every properties about the Horadam sequences have a corresponding right analog.

A right Horadam sequence is

$\hat{\mathbf{w}}⟨a,b;p,q⟩=({\hat{w}}_n)$, where

$({\hat{w}}_n)$ satisfies the recurrence relation

$$\begin{array}{rl}{\hat{w}}_0& =a,{\hat{w}}_1=b,\\ {\hat{w}}_n& ={\hat{w}}_{n-1}p-{\hat{w}}_{n-2}q.\end{array}$$

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$.

• $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)$.

Properties

Describe Horadam sequences by Lucas sequences

• $w_n⟨a+a^{\prime },b+b^{\prime };p,q⟩=w_n⟨a,b;p,q⟩+w_n⟨a^{\prime },b^{\prime };p,q⟩$.
• $w_n⟨ac,bc;p,q⟩=w_n⟨a,b;p,q⟩\cdot c$.
• If
  $p,q\sim r$, then
  $w_n⟨ra,rb;p,q⟩=r\cdot w_n⟨a,b;p,q⟩$.

Let

$(w_n)=\mathbf{w}⟨a,b;p,q⟩$ and

$(w_n^{\prime })=\mathbf{w}⟨a^{\prime },b^{\prime };p,q⟩$.
Then we have the recurrence relations

$$\begin{array}{rl}{w}_n+w_n^{\prime }& =p{w}_{n-1}-q{w}_{n-2}+p{w}_{n-1}^{\prime }-q{w}_{n-2}^{\prime }\\ & =p(w_{n-1}+w_{n-1}^{\prime })-q(w_{n-2}+w_{n-2}^{\prime }),\end{array}$$

$$\begin{array}{rl}{w}_{n}c& =(p{w}_{n-1}-q{w}_{n-2})c\\ & =p(w_{n-1}c)-q(w_{n-2}c).\end{array}$$

$$\begin{array}{rl}r{w}_n& =r(p{w}_{n-1}-q{w}_{n-2})\\ & =p(r{w}_{n-1})-q(r{w}_{n-2}).\end{array}$$

Let

$(u_n)=\mathbf{u}⟨p,q⟩$ where

$p,q\in R$, and let

$a,b\in {}_{R}M$, then

• $w_n⟨0,b;p,q⟩=u_{n}b$.
• $w_n⟨a,b;p,q⟩=u_{n}b-u_{n-1}qa$.

Let

$(w_n)=\mathbf{w}⟨0,b;p,q⟩$.
If

$w_k=u_{k}b$ and

$w_{k+1}=u_{k+1}b$, we have

$$\begin{array}{rl}{w}_{k+2}& =p{w}_{k+1}-q{w}_k\\ & =(p{u}_{k+1}-q{u}_k)b=u_{k+2}b.\end{array}$$
Thus, since

$w_0=0=0b=u_{0}b$ and

$w_1=b=1b=u_{1}b$, we have

$w_n=u_{n}b$ by induction.

Moreover,

$$\begin{array}{rl}{w}_n⟨a,b;p,q⟩& =w_n⟨0,b;p,q⟩+w_n⟨a,0;p,q⟩\\ & =w_n⟨0,b;p,q⟩+w_{n-1}⟨0,-qa;p,q⟩\\ & =u_{n}b-u_{n-1}qa.\end{array}$$

Multipermutations of two objects

Let

${\mathfrak{S}}_2^{(m,k)}⟨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)}$.

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$.

• $|{\mathfrak{S}}_2^{(m,k)}|=(\genfrac{}{}{0ex}{}{m+k}{k})$.
• $S(m,k)=\{\begin{array}{ll}0& m<0\text{ or }k<0;\\ q^k& m=0;\\ p^n& k=0.\end{array}$
• $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)=(\genfrac{}{}{0ex}{}{m+k}{k})p^m{q}^k$.

If we write

$\sigma (1)\sigma (2)\cdots \sigma (m+k)$ for

$\sigma \in {\mathfrak{S}}_2^{(m,k)}$, then we have

$$\begin{array}{rl}{\mathfrak{S}}_2^{(3,2)}=\{& p^3{q}^2,p^{2}qpq,pq{p}^{2}q,q{p}^{3}q,p^2{q}^{2}p,\\ & pqpqp,q{p}^{2}qp,p{q}^2{p}^2,qpq{p}^2,q^2{p}^3\},\end{array}$$
and

$|{\mathfrak{S}}_2^{(3,2)}|=10=(\genfrac{}{}{0ex}{}{3+2}{2})$.

Let

$(u_n)=\mathbf{u}⟨p,q⟩$, then we have

$$u_n=\sum _{k=0}^{\mathrm{\infty }}(-1{)}^{k}S(n-2k-1,k).$$
Moreover, if

$p\sim q$, we have

$$u_n=\sum _{k=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{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}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{n-k-1}{k})(\frac{-q}{p^2}{)}^k.$$

The

$\mathrm{\infty }$ is only for convenience, since

$S(n-2k-1,k)=0$ if

$k>(n-1)/2$.

Let

$s_n=\sum _{k=0}^{\mathrm{\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{array}{rl}{s}_{n+2}& =\sum _{k=0}^{\mathrm{\infty }}(-1{)}^{k}S(n-2k+1,k)\\ & =\sum _{k=0}^{\mathrm{\infty }}(-1{)}^{k}pS(n-2k,k)+\sum _{k=1}^{\mathrm{\infty }}(-1{)}^{k}qS(n-2k+1,k-1)\\ & =\sum _{k=0}^{\mathrm{\infty }}(-1{)}^{k}pS(n-2k,k)-\sum _{k=0}^{\mathrm{\infty }}(-1{)}^{k}qS(n-2k-1,k)\\ & =p{s}_{n+1}-q{s}_n.\end{array}$$
Therefore

$(s_n)=\mathbf{u}⟨p,q⟩=(u_n)$ by induction.

Let

$(u_n)=\mathbf{u}⟨p,q⟩$, then we have

$$u_n=u_{n-1}p-u_{n-2}q.$$
This is to say that

$\hat{\mathbf{u}}⟨p,q⟩=\mathbf{u}⟨p,q⟩$.

If

$p,q\sim r$, then we have

• $u_n⟨pr,q{r}^2⟩=r^{n-1}\cdot u_n⟨p,q⟩$.
• $w_n⟨a,b;pr,q{r}^2⟩=r^{n-1}\cdot w_n⟨ra,b;p,q⟩$.

Product formulae

Let

$r\otimes \left[\begin{array}{c}n\\ m\end{array}\right]$ denote the product

${\hat{w}}_n⟨a^{\prime },b^{\prime };p,q⟩\cdot r\cdot w_m⟨a,b;p,q⟩$, and

$\left[\begin{array}{c}n\\ m\end{array}\right]=1\otimes \left[\begin{array}{c}n\\ m\end{array}\right]$.

The product is an element in the tensor product

$M{\otimes }_{R}M$.
The notation here is only for convenience :P.

Note that if

$M=R$ and

$r\sim ({\hat{w}}_n)$, then

$r\otimes \left[\begin{array}{c}n\\ m\end{array}\right]=r\cdot \left[\begin{array}{c}n\\ m\end{array}\right]$.

For any

$n$,

$m$, and

$k$, we have

$$\left[\begin{array}{c}n\\ m\end{array}\right]-q\otimes \left[\begin{array}{c}n-1\\ m-1\end{array}\right]=\left[\begin{array}{c}n+k\\ m-k\end{array}\right]-q\otimes \left[\begin{array}{c}n+k-1\\ m-k-1\end{array}\right].$$

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}.$$

We have

$$\begin{array}{rl}& \left[\begin{array}{c}n\\ m\end{array}\right]-q\otimes \left[\begin{array}{c}n-1\\ m-1\end{array}\right]\\ & =(p\otimes \left[\begin{array}{c}n\\ m-1\end{array}\right]-q\otimes \left[\begin{array}{c}n\\ m-2\end{array}\right])-(p\otimes \left[\begin{array}{c}n\\ m-1\end{array}\right]-\left[\begin{array}{c}n+1\\ m-1\end{array}\right])\\ & =\left[\begin{array}{c}n+1\\ m-1\end{array}\right]-q\otimes \left[\begin{array}{c}n\\ m-2\end{array}\right].\end{array}$$
Continue in this manner, then we get the result.

Similarly, if

$p\sim q$, then we have

$$q^r\otimes \left[\begin{array}{c}n\\ m\end{array}\right]-q^{r+1}\otimes \left[\begin{array}{c}n-1\\ m-1\end{array}\right]=q^r\otimes \left[\begin{array}{c}n+k\\ m-k\end{array}\right]-q^{r+1}\otimes \left[\begin{array}{c}n+k-1\\ m-k-1\end{array}\right].$$

If

$p\sim q$, then for any

$n$,

$m$,

$k$,

$r$, and

$s$, we have

$$q^r\otimes \left[\begin{array}{c}n\\ m\end{array}\right]-q^r\otimes \left[\begin{array}{c}n+k\\ m-k\end{array}\right]=q^{r+s}\otimes \left[\begin{array}{c}n-s\\ m-s\end{array}\right]-q^{r+s}\otimes \left[\begin{array}{c}n+k-s\\ m-k-s\end{array}\right].$$

Subsequences

If

$p\sim q$, then we have

$u_k{v}_k=u_{2k}=v_k{u}_k$.

Since

$v_0=2$,

$v_1=p$, and

$(u_n)=({\hat{u}}_n)$, by the product formula, we have

$$\begin{array}{rl}{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{array}$$
Thus, since

$p\sim q$, we have

$$\begin{array}{rl}{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{array}$$
Continue in this manner, we get

$u_k{v}_k-u_{2k}=q^k(0-0)=0$.

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={\displaystyle \frac{u_{2k}}{u_k}}$.

Let

$(w_n)=\mathbf{w}⟨a,b;p,q⟩$ and

$(v_k)=\mathbf{v}⟨p,q⟩$.
If

$p\sim q$, then

$$(w_{kn+t}{)}_{n=0}^{\mathrm{\infty }}=\mathbf{w}⟨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.

Let

$(s_n)=(w_{kn})$.
It is sufficient to show that

$(s_n)=\mathbf{w}⟨w_0,w_k;v_k,q^k⟩$.

Let

$\gamma =w_{kn+1}$ and

$(u_k)=\mathbf{u}⟨p,q⟩$, then we have

$$\begin{array}{rl}{s}_{n+m}& =w_{km}⟨s_n,\gamma ;p,q⟩\\ & =u_{km}\gamma -u_{km-1}q{s}_n.\end{array}$$
Thus we get

$u_k\gamma =s_{n+1}+u_{k-1}q{s}_n$.
Then we have

$$\begin{array}{rl}{u}_k{s}_{n+2}& =u_k(u_{2k}\gamma -u_{2k-1}q{s}_n)\\ & =u_{2k}(u_k\gamma -u_{k-1}q{s}_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{array}$$
which form a recurrence relation and gives

$(u_k{s}_n{)}_{n=0}^{\mathrm{\infty }}=u_k\cdot \mathbf{w}⟨w_0,w_k;v_k,q^k⟩$.

Therefore, since the

$u_k$ is cancellative (why?), we get

$$(s_n)=\mathbf{w}⟨w_0,w_k;v_k,q^k⟩.$$

If

$p\sim q$, then we have

$$u_{kn}=w_k⟨0,u_n;v_n,q^n⟩=u_n\cdot u_k⟨v_n,q^n⟩.$$

If

$p\sim q$, then

$$\frac{u_{2n}}{u_n}=u_2⟨v_n,q^n⟩=v_n,\frac{u_{3n}}{u_n}=u_3⟨v_n,q^n⟩=v_n^2-q^n.$$

---

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.
• 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.