This paper was converted on www.awesomepapers.org from LaTeX by an anonymous user.
Want to know more? Visit the Converter page.

A RECURRENCE RELATION ASSOCIATED WITH UNIT-PRIMITIVE MATRICES

Byeong-Gil Choe111Chonnam National University, [email protected], Hyeong-Kwan Ju222Chonnam National University, [email protected] 333corresponding author, Department of Mathematics, Chonnam National University, Gwangju, Republic of Korea
Abstract

In this paper we obtained several properties that the characteristic polynomials of the unit-primitive matrix satisfy. In addition, using these properties we have shown that the recurrence relation given as in the formula (1) is true. In fact, Xin and Zhong([4]) showed it earlier. However, we provide simpler method here.

1 Introduction

The unit-primitive matrix comes naturally when computing discrete volumes of certain graph polytopes. Below, the related terms and results will be explained.
For a given positive integer mm, we let B​(m)=(bi​j)B(m)=(b_{ij}) (1≤i,j≤m)(1\leq i,j\leq m) be a square matrix of size m×mm\times m satisfying

bi​j={1i+j≤m+10otherwiseb_{ij}=\begin{cases}1&i+j\leq m+1\\ 0&\text{otherwise}\end{cases}

We call this type of upper triangular matrix a unit-primitive matrix of size mm. For example, unit-primitive matrix of size 5 and its inverse matrix are as follows.

B​(5)=(1111111110111001100010000),B​(5)−1=(000010001−1001−1001−1001−1000)B(5)=\begin{pmatrix}[r]1&1&1&1&1\\ 1&1&1&1&0\\ 1&1&1&0&0\\ 1&1&0&0&0\\ 1&0&0&0&0\end{pmatrix},\quad B(5)^{-1}=\begin{pmatrix}[r]0&0&0&0&1\\ 0&0&0&1&-1\\ 0&0&1&-1&0\\ 0&1&-1&0&0\\ 1&-1&0&0&0\end{pmatrix}

If MM is a square matrix, we denote the sum of all entries of MM by s​(M)s(M). So, s​(M)=ut​M​us(M)=u^{t}Mu for the column vector uu all of whose entries are 1. We define a bi-variate sequence b​(n,m)​(n,m≥0)b(n,m)(n,m\geq 0) as follows.

b​(n,m)={1n=0 or m=0s​(B​(m+1)n−1)n and m positive\quad b(n,m)=\begin{cases}1&\text{$n$=0 or $m$=0}\\ s\big{(}B(m+1)^{n-1}\big{)}&\text{$n$ and $m$ positive}\end{cases}
nn mm 0 1 2 3 4 5 6 7 8 9 ⋯\cdots
0 1 1 1 1 1 1 1 1 1 1 ⋯\cdots
1 1 2 3 4 5 6 7 8 9 10 ⋯\cdots
2 1 3 6 10 15 21 28 36 45 55 ⋯\cdots
3 1 5 14 30 55 91 140 204 285 385 ⋯\cdots
4 1 8 31 85 190 371 658 1086 1695 2530 ⋯\cdots
5 1 13 70 246 671 1547 3164 5916 10317 17017 ⋯\cdots
⋮\vdots ⋮\vdots ⋮\vdots ⋮\vdots ⋮\vdots ⋮\vdots ⋮\vdots ⋮\vdots ⋮\vdots ⋮\vdots ⋮\vdots
Table 1: Table of b​(n,m)b(n,m)

Our main concern is that the following recurrence relation holds for the sequence (b​(n,m))n,m≥0(b(n,m))_{n,m\geq 0}.

b​(n,m)=b​(n,m−1)+∑k≥0b​(2​k,m−1)​b​(n−1−2​k,m)b(n,m)=b(n,m-1)+\sum_{k\geq 0}b(2k,m-1)b(n-1-2k,m) (1)

This number appeared in chemistry as the number of Kekulé structures of the benzenoid hydrocarbons.(See [1], [4] for details.). It is also listed with an id A050446 in [3]). Let Fm​(x)=∑n≥0b​(n,m)​xnF_{m}(x)=\sum_{n\geq 0}b(n,m)x^{n}, Gn​(x)=∑m≥0b​(n,m)​xmG_{n}(x)=\sum_{m\geq 0}b(n,m)x^{m}, Qm​(x)Q_{m}(x) =det(I−x​B​(m))\det{(I-xB(m))} and Rm​(x)=det(0ut−uI−x​B​(m))R_{m}(x)=\det{\begin{pmatrix}0&u^{t}\\ -u&I-xB(m)\end{pmatrix}}, where u=(1,1,⋯,1)t∈ℝmu=(1,1,\cdots,1)^{t}\in\mathbb{R}^{m}.
The sequence (Gn​(y))n≥0(G_{n}(y))_{n\geq 0} of the Ehrhart series is well analyzed in detail by Xin and Zhong([4]). We want to describe our main results in a slightly different way, however. Now, let M∗M^{*} be an adjugate matrix of the square matrix MM.

Lemma 1.

s​(M∗)=det(0ut−uM)s(M^{*})=\det{\begin{pmatrix}0&u^{t}\\ -u&M\end{pmatrix}} for all matrix M of size n×nn\times n.

Proof.

Let mim_{i} be the iith column of the matrix MM, and

Mi=det(m1,⋯,mi−1,u,mi+1,⋯,mn).M_{i}=\det(m_{1},\cdots,m_{i-1},u,m_{i+1},\cdots,m_{n}).

Then

s​(M∗)=\displaystyle s(M^{*})= ut​M∗​u=ut​[M1,M2,⋯,Mn]t\displaystyle u^{t}M^{*}u=u^{t}[M_{1},M_{2},\cdots,M_{n}]^{t}
=\displaystyle= det(u,m2,m3,⋯,mn)+det(m1,u,m3,⋯,mn)\displaystyle\det(u,m_{2},m_{3},\cdots,m_{n})+\det(m_{1},u,m_{3},\cdots,m_{n})
+⋯+det(m1,m2,m3,⋯,u)\displaystyle+\cdots+\det(m_{1},m_{2},m_{3},\cdots,u)
=\displaystyle= det(u,m2,m3,⋯,mn)−det(u,m1,m3,⋯,mn)\displaystyle\det(u,m_{2},m_{3},\cdots,m_{n})-\det(u,m_{1},m_{3},\cdots,m_{n})
+⋯+(−1)n+1​det(u,m1,m2,⋯,mn−1)\displaystyle+\cdots+(-1)^{n+1}\det(u,m_{1},m_{2},\cdots,m_{n-1})
=\displaystyle= det(0ut−uM).\displaystyle\ \det{\begin{pmatrix}0&u^{t}\\ -u&M\end{pmatrix}}.

∎

Theorem 2.

Let Em​(x)=∑n≥0b​(n+1,m)​xnE_{m}(x)=\sum_{n\geq 0}b(n+1,m)x^{n}. Then

Em​(x)=det(0ut−uI−x​B​(m+1))det(Im+1−x​B​(m+1))=Rm+1​(x)Qm+1​(x)E_{m}(x)=\frac{\det\begin{pmatrix}0&u^{t}\\ -u&I-xB(m+1)\end{pmatrix}}{\det(I_{m+1}-xB(m+1))}=\frac{R_{m+1}(x)}{Q_{m+1}(x)}
Proof.
Em​(x)\displaystyle E_{m}(x) =∑n≥0b​(n+1,m)​xn=∑n≥0s​(B​(m+1)n)​xn\displaystyle=\sum_{n\geq 0}b(n+1,m)x^{n}=\sum_{n\geq 0}s(B(m+1)^{n})x^{n}
=s​(∑n≥0(x​B​(m+1))n)=s​[I−x​B​(m+1)−1]\displaystyle=s\left(\sum_{n\geq 0}(xB(m+1))^{n}\right)=s\left[I-xB(m+1)^{-1}\right]
=s​((I−x​B​(m+1))∗det(I−x​B​(m+1)))=1Qm+1​(x)​s​((I−x​B​(m+1))∗)\displaystyle=s\left(\frac{(I-xB(m+1))^{*}}{\det(I-xB(m+1))}\right)=\frac{1}{Q_{m+1}(x)}s((I-xB(m+1))^{*})
=1Qm+1​[ut​(I−x​B​(m+1))∗​u]\displaystyle=\frac{1}{Q_{m+1}}\left[u^{t}(I-xB(m+1))^{*}u\right]
=1Qm+1​(x)​det(0ut−uI−x​B​(m+1))=Rm+1​(x)Qm+1​(x).\displaystyle=\frac{1}{Q_{m+1}(x)}\det\begin{pmatrix}0&u^{t}\\ -u&I-xB(m+1)\end{pmatrix}=\frac{R_{m+1}(x)}{Q_{m+1}(x)}.

∎

2 Properties of Qm​(x)Q_{m}(x)

In this section we list the properties of Qm​(x)Q_{m}(x) and prove them.

Theorem 3.

Qm​(x)=det(I−x​B​(m))Q_{m}(x)=\det(I-xB(m)) satisfies the following properties.

(1)\displaystyle(1) Qm​(x)=−x​Qm−1​(−x)+Qm−2​(x)(m≥2), and\displaystyle\quad Q_{m}(x)=-xQ_{m-1}(-x)+Q_{m-2}(x)\quad(m\geq 2),\text{ and}
Q0​(x)=1,Q1​(x)=1−x.\displaystyle\quad Q_{0}(x)=1,Q_{1}(x)=1-x.
(2)\displaystyle(2) Qm​(x)​Qm+1​(x)−Qm​(−x)​Qm+1​(−x)=2(m≥0).\displaystyle\quad Q_{m}(x)Q_{m+1}(x)-Q_{m}(-x)Q_{m+1}(-x)=2\quad(m\geq 0).
(3)\displaystyle(3) Qm+1​(x)​Qm+1​(−x)−Qm+2​(x)​Qm​(−x)=x(m≥0).\displaystyle\quad Q_{m+1}(x)Q_{m+1}(-x)-Q_{m+2}(x)Q_{m}(-x)=x\quad(m\geq 0).
(4)\displaystyle(4) Qm​(x)=x​Rm​(x)=Qm−1​(−x)(m≥1).\displaystyle\quad Q_{m}(x)=xR_{m}(x)=Q_{m-1}(-x)\quad(m\geq 1).
Proof.

(1) For m≥2m\geq 2,

Qm​(x)\displaystyle Q_{m}(x) =|1−x−x−x⋯−x−x−x−x1−x−x⋯−x−x0−x−x1−x⋯−x00⋮⋮⋮⋮⋮⋮⋮−x−x0⋯010−x00⋯001|\displaystyle=\begin{vmatrix}1-x&-x&-x&\cdots&-x&-x&-x\\ -x&1-x&-x&\cdots&-x&-x&0\\ -x&-x&1-x&\cdots&-x&0&0\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ -x&-x&0&\cdots&0&1&0\\ -x&0&0&\cdots&0&0&1\\ \end{vmatrix}
=|1−x−x⋯−x−x−x01−x−x⋯−x−x00−x1−x⋯−x00⋮⋮⋮⋮⋮⋮⋮0−x0⋯010000⋯001|+|−x−x−x⋯−x−x−x−x1−x−x⋯−x−x0−x−x1−x⋯−x00⋮⋮⋮⋮⋮⋮⋮−x−x0⋯010−x00⋯001|\displaystyle=\begin{vmatrix}1&-x&-x&\cdots&-x&-x&-x\\ 0&1-x&-x&\cdots&-x&-x&0\\ 0&-x&1-x&\cdots&-x&0&0\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ 0&-x&0&\cdots&0&1&0\\ 0&0&0&\cdots&0&0&1\\ \end{vmatrix}+\begin{vmatrix}-x&-x&-x&\cdots&-x&-x&-x\\ -x&1-x&-x&\cdots&-x&-x&0\\ -x&-x&1-x&\cdots&-x&0&0\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ -x&-x&0&\cdots&0&1&0\\ -x&0&0&\cdots&0&0&1\\ \end{vmatrix}
by the splitting of the first column
=det(I−x​B​(m−2))+|−x00⋯000−x10⋯00x−x01⋯0xx⋮⋮⋮⋮⋮⋮⋮−x0x⋯x1+xx−xxx⋯xx1+x|\displaystyle=\det(I-xB(m-2))+\begin{vmatrix}-x&0&0&\cdots&0&0&0\\ -x&1&0&\cdots&0&0&x\\ -x&0&1&\cdots&0&x&x\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ -x&0&x&\cdots&x&1+x&x\\ -x&x&x&\cdots&x&x&1+x\\ \end{vmatrix}
=Qm−2​(x)−x​|10⋯00x01⋯0xx⋮⋮⋮⋮⋮⋮0x⋯x1+xxxx⋯xx1+x|\displaystyle=Q_{m-2}(x)-x\begin{vmatrix}1&0&\cdots&0&0&x\\ 0&1&\cdots&0&x&x\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ 0&x&\cdots&x&1+x&x\\ x&x&\cdots&x&x&1+x\\ \end{vmatrix}
=Qm−2​(x)−x​|1+xx⋯xxxx1+x⋯xx0⋮⋮⋮⋮⋮⋮xx⋯010x0⋯001|\displaystyle=Q_{m-2}(x)-x\begin{vmatrix}1+x&x&\cdots&x&x&x\\ x&1+x&\cdots&x&x&0\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ x&x&\cdots&0&1&0\\ x&0&\cdots&0&0&1\\ \end{vmatrix}
in reverse order of rows and columns in the second determinant
=Qm−2​(x)−x​Qm−1​(−x)\displaystyle=Q_{m-2}(x)-xQ_{m-1}(-x)

(2) Use induction on mm. Formula (2) holds for m=1m=1 since

Q0​(x)​Q1​(x)+Q0​(−x)​Q1​(−x)=(1−x)​(1−x−x2)+(1+x)​(1+x−x2)=2Q_{0}(x)Q_{1}(x)+Q_{0}(-x)Q_{1}(-x)=(1-x)(1-x-x^{2})+(1+x)(1+x-x^{2})=2

We assume that formula (2) holds for m≤km\leq k.

Qk+1​(x)​Qk+2​(x)+Qk+1​(−x)​Qk+2​(−x)\displaystyle Q_{k+1}(x)Q_{k+2}(x)+Q_{k+1}(-x)Q_{k+2}(-x)
=Qk+1(x)(−xQk+1(−x)+Qk(x))+Qk+1(−x)(xQk+1(x)+Qk(−x)\displaystyle=Q_{k+1}(x)(-xQ_{k+1}(-x)+Q_{k}(x))+Q_{k+1}(-x)(xQ_{k+1}(x)+Q_{k}(-x)
=Qk+1​(x)​Qk​(x)+Qk+1​(−x)​Qk​(−x)=2.\displaystyle=Q_{k+1}(x)Q_{k}(x)+Q_{k+1}(-x)Q_{k}(-x)=2.

(3) Similar to the previous one, we also use induction on m.m. Formula (3) holds for m=0m=0 since

Q1​(x)​Q1​(−x)−Q2​(x)​Q0​(−x)=(1−x)​(1+x)−(1−x−x2)​(1)=x.Q_{1}(x)Q_{1}(-x)-Q_{2}(x)Q_{0}(-x)=(1-x)(1+x)-(1-x-x^{2})(1)=x.

We assume that formula (3) holds for m≤km\leq k.

Qk+2​(x)​Qk+2​(−x)−Qk+3​Qk+1​(−x)\displaystyle Q_{k+2}(x)Q_{k+2}(-x)-Q_{k+3}Q_{k+1}(-x)
=Qk+2​(x)​(x​Qk+1​(x)+Qk​(−x))−(−x​Qk+2​(−x)+Qk+1​(x))​Qk+1​(−x)\displaystyle=Q_{k+2}(x)(xQ_{k+1}(x)+Q_{k}(-x))-(-xQ_{k+2}(-x)+Q_{k+1}(x))Q_{k+1}(-x)
=x​[Qk+1​(x)​Qk+2​(x)+Qk+1​(−x)​Qk+2​(−x)]+[Qk​(−x)​Qk+2​(x)−Qk+1​(x)​Qk+1​(−x)]\displaystyle=x\left[Q_{k+1}(x)Q_{k+2}(x)+Q_{k+1}(-x)Q_{k+2}(-x)\right]+\left[Q_{k}(-x)Q_{k+2}(x)-Q_{k+1}(x)Q_{k+1}(-x)\right]
=2​x−x=x,\displaystyle=2x-x=x,

by the formula (2) and the induction assumption.

(4)

Qm​(x)+x​Rm​(x)\displaystyle Q_{m}(x)+xR_{m}(x)
=det(I−x​B​(m))+x​det(0ut−uI−x​B​(m))\displaystyle=\det(I-xB(m))+x\det\begin{pmatrix}0&u^{t}\\ -u&I-xB(m)\end{pmatrix}
=det(1ut−x​uI−x​B​(m))\displaystyle=\det\begin{pmatrix}1&u^{t}\\ -xu&I-xB(m)\end{pmatrix}
=|1111⋯111−x1−x−x−x⋯−x−x−x−x−x1−x−x⋯−x−x0−x−x−x1−x⋯−x00⋮⋮⋮⋮⋮⋮⋮−x−x−x−x⋯100−x−x−x0⋯010−x−x00⋯001|\displaystyle=\begin{vmatrix}1&1&1&1&\cdots&1&1&1\\ -x&1-x&-x&-x&\cdots&-x&-x&-x\\ -x&-x&1-x&-x&\cdots&-x&-x&0\\ -x&-x&-x&1-x&\cdots&-x&0&0\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ -x&-x&-x&-x&\cdots&1&0&0\\ -x&-x&-x&0&\cdots&0&1&0\\ -x&-x&0&0&\cdots&0&0&1\\ \end{vmatrix}
=|1111⋯1110100⋯0000010⋯00x0001⋯0xx⋮⋮⋮⋮⋮⋮⋮0000⋯1+xxx000x⋯x1+xx00xx⋯xx1+x|\displaystyle=\begin{vmatrix}1&1&1&1&\cdots&1&1&1\\ 0&1&0&0&\cdots&0&0&0\\ 0&0&1&0&\cdots&0&0&x\\ 0&0&0&1&\cdots&0&x&x\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ 0&0&0&0&\cdots&1+x&x&x\\ 0&0&0&x&\cdots&x&1+x&x\\ 0&0&x&x&\cdots&x&x&1+x\\ \end{vmatrix}
=|10⋯00x01⋯0xx⋮⋮⋮⋮⋮⋮00⋯1+xxx0x⋯x1+xxxx⋯xx1+x|\displaystyle=\begin{vmatrix}1&0&\cdots&0&0&x\\ 0&1&\cdots&0&x&x\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ 0&0&\cdots&1+x&x&x\\ 0&x&\cdots&x&1+x&x\\ x&x&\cdots&x&x&1+x\\ \end{vmatrix}
=|1+xx⋯xxxx1+x⋯xx0⋮⋮⋮⋮⋮⋮xx⋯100xx⋯010x0⋯001|\displaystyle=\begin{vmatrix}1+x&x&\cdots&x&x&x\\ x&1+x&\cdots&x&x&0\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ x&x&\cdots&1&0&0\\ x&x&\cdots&0&1&0\\ x&0&\cdots&0&0&1\\ \end{vmatrix}
=Qm−1​(−x)\displaystyle=Q_{m-1}(-x)

∎

Here is another interesting property on (Qm​(x))m≥0(Q_{m}(x))_{m\geq 0}. For reference its ordinary generating function is given below. (See [2] for the proof.)

Theorem 4.
∑m≥0Qm​(x)​tm=(1+t)​(1−t2−x​t)(1−t2)2+(x​t)2.\sum_{m\geq 0}Q_{m}(x)t^{m}=\frac{(1+t)(1-t^{2}-xt)}{(1-t^{2})^{2}+(xt)^{2}}.

3 Recurrence Relation of the Sequence b​(n,m)b(n,m)

Note that Fm​(x)=1+x​Em​(x).F_{m}(x)=1+xE_{m}(x). By the property (4) of Theorem3, we obtain the generating function Fm​(x)F_{m}(x) of the sequence (b​(n,m))n≥0.\left(b(n,m)\right)_{n\geq 0}.

Theorem 5.
Fm​(x)=Qm​(−x)Qm+1​(x).F_{m}(x)=\frac{Q_{m}(-x)}{Q_{m+1}(x)}.
Proof.
Fm​(x)\displaystyle F_{m}(x) =1+x​Em​(x)=1+x​Rm+1​(x)Qm+1​(x)\displaystyle=1+xE_{m}(x)=1+x\frac{R_{m+1}(x)}{Q_{m+1}(x)}
=Qm+1+x​Rm+1​(x)Qm+1​(x)=Qm​(−x)Qm+1​(x).\displaystyle=\frac{Q_{m+1}+xR_{m+1}(x)}{Q_{m+1}(x)}=\frac{Q_{m}(-x)}{Q_{m+1}(x)}.

∎

Similar to the Chebyshev function of the second kind, Fm​(x)F_{m}(x) has an expression by a trigonometric function as in the next theorem.(For details, see references [2] and [4].)

Theorem 6.

For each positive integer m,m,

Fm​(x)=(−1)m+1​cos⁡(2​m+12)​θcos⁡(2​m+32)​θ=sin⁡(m+1)​θ−sin⁡m​θsin⁡(m+2)​θ−sin⁡(m+1)​θ,F_{m}(x)=(-1)^{m+1}\frac{\cos(\frac{2m+1}{2})\theta}{\cos(\frac{2m+3}{2})\theta}=\frac{\sin(m+1)\theta-\sin m\theta}{\sin(m+2)\theta-\sin(m+1)\theta},

where θ=cos−1⁡((−1)m​x2).\theta=\cos^{-1}\Big{(}\frac{(-1)^{m}x}{2}\Big{)}.

Theorem 7.

Generating function Fm​(x)F_{m}(x) satisfies the continued fraction property:

Fm​(x)=1−x+Fm−1​(−x),F0​(x)=11−x.F_{m}(x)=\frac{1}{-x+F_{m-1}(-x)},\ F_{0}(x)=\frac{1}{1-x}.

First three formulas are listed here:

F1​(x)=1−x+F0​(−x)=1−x+1x+1=1+x1−x−x2=Q1​(−x)Q2​(x)\displaystyle F_{1}(x)=\frac{1}{-x+F_{0}(-x)}=\frac{1}{-x+\frac{1}{x+1}}=\frac{1+x}{1-x-x^{2}}=\frac{Q_{1}(-x)}{Q_{2}(x)}
F2​(x)=1−x+F1​(−x)=1+x−x21−2​x−x2+x3=Q2​(−x)Q3​(x)\displaystyle F_{2}(x)=\frac{1}{-x+F_{1}(-x)}=\frac{1+x-x^{2}}{1-2x-x^{2}+x^{3}}=\frac{Q_{2}(-x)}{Q_{3}(x)}
F3​(x)=1−x+F2​(−x)=1+2​x−x2−x31−2​x−3​x2+x3+x4=Q3​(−x)Q4​(x)\displaystyle F_{3}(x)=\frac{1}{-x+F_{2}(-x)}=\frac{1+2x-x^{2}-x^{3}}{1-2x-3x^{2}+x^{3}+x^{4}}=\frac{Q_{3}(-x)}{Q_{4}(x)}
Proof.

For a positive integer m≥2m\geq 2, if we use the property (1) of Theorem3. we obtain the following:

Fm​(x)\displaystyle F_{m}(x) =Qm​(−x)Qm+1​(x)=Qm​(−x)−x​Qm​(−x)+Qm−1​(x)\displaystyle=\frac{Q_{m}(-x)}{Q_{m+1}(x)}=\frac{Q_{m}(-x)}{-xQ_{m}(-x)+Q_{m-1}(x)}
=1−x+Gm−1​(x)Qm​(−x)=1−x+Fm−1​(−x).\displaystyle=\frac{1}{-x+\frac{G_{m-1}(x)}{Q_{m}(-x)}}=\frac{1}{-x+F_{m-1}(-x)}.

∎

Theorem 8.

Let the sequence {c​(n,m)}n,m≥0\{c(n,m)\}_{n,m\geq 0} satisfies the recurrence relation stated as below:

c​(n,m)=c​(n,m−1)+∑k≥0c​(2​k,m−1)​c​(n−1−2​k,m)​(c​(n,0)=1,∀n≥0)c(n,m)=c(n,m-1)+\sum_{k\geq 0}c(2k,m-1)c(n-1-2k,m)(c(n,0)=1,\forall n\geq 0) (2)

Then c​(n,m)=b​(n,m)c(n,m)=b(n,m) for all nonnegative integers nn, mm.

In fact, this has been proved by Xin and Zhong([4]). However, we proved it another way by using properties (2) and (3) of Theorem3 as below. Our proof seems to be short and simple compared to their lengthy proof which amounts to several pages.

Proof.

Let

Cm​(x)=∑n≥0c​(n,m)​xn.C_{m}(x)=\sum_{n\geq 0}c(n,m)x^{n}.

The proof is done if we show that Cm​(x)=Fm​(x)C_{m}(x)=F_{m}(x) for all m≥0m\geq 0. Note that from the recurrence relation (2) we get the following formula:

Cm​(x)=Cm−1​(x)+x​Cm−1e​(x)​Cm​(x)​ with ​C0​(x)=11−x,C_{m}(x)=C_{m-1}(x)+xC^{e}_{m-1}(x)C_{m}(x)\text{ with }C_{0}(x)=\frac{1}{1-x}, (3)

where

Cme​(x)=12​(Cm​(x)+Cm​(−x)).C^{e}_{m}(x)=\frac{1}{2}(C_{m}(x)+C_{m}(-x)).

From the equation (3), we obtain the following:

Cm​(x)=Cm−1​(x)1−x​(Cm−1​(x)+Cm−1​(−x))/2C_{m}(x)=\frac{C_{m-1}(x)}{1-x(C_{m-1}(x)+C_{m-1}(-x))/2} (4)

We will use mathematical induction on mm to prove that Cm​(x)=Fm​(x)C_{m}(x)=F_{m}(x) for all m≥0m\geq 0. It is obvious that C0​(x)=11−x=F0​(x)C_{0}(x)=\frac{1}{1-x}=F_{0}(x). We assume that Ci​(x)=Fi​(x)C_{i}(x)=F_{i}(x) for all i≤m−1i\leq m-1. By the assumption, from the formula(4) , we have

Cm​(x)\displaystyle C_{m}(x) =Fm−1​(x)1−x​(Fm−1​(x)+Fm−1​(−x))/2\displaystyle=\frac{F_{m-1}(x)}{1-x(F_{m-1}(x)+F_{m-1}(-x))/2}
=Qm−1​(−x)Qm​(x)1−x​(Qm−1​(−x)Qm​(x)+Qm−1​(x)Qm​(−x))/2\displaystyle=\frac{\frac{Q_{m-1}(-x)}{Q_{m}(x)}}{1-x\left(\frac{Q_{m-1}(-x)}{Q_{m}(x)}+\frac{Q_{m-1}(x)}{Q_{m}(-x)}\right)/2}
=Qm−1​(−x)Qm​(x)1−x2​Qm−1​(−x)​Qm​(−x)+Qm−1​(x)​Qm​(x)Qm​(x)​Qm​(−x)\displaystyle=\frac{\frac{Q_{m-1}(-x)}{Q_{m}(x)}}{1-\frac{x}{2}\frac{Q_{m-1}(-x)Q_{m}(-x)+Q_{m-1}(x)Q_{m}(x)}{Q_{m}(x)Q_{m}(-x)}}
=Qm−1​(−x)Qm​(x)1−xQm​(x)​Qm​(−x)=Qm−1​(−x)​Qm​(−x)Qm​(x)​Qm​(−x)−x=Qm−1​(−x)​Qm​(−x)Qm+1​(x)​Qm−1​(−x)\displaystyle=\frac{\frac{Q_{m-1}(-x)}{Q_{m}(x)}}{1-\frac{x}{Q_{m}(x)Q_{m}(-x)}}=\frac{Q_{m-1}(-x)Q_{m}(-x)}{Q_{m}(x)Q_{m}(-x)-x}=\frac{Q_{m-1}(-x)Q_{m}(-x)}{Q_{m+1}(x)Q_{m-1}(-x)}
=Qm​(−x)Qm+1​(x)=Fm​(x).\displaystyle=\frac{Q_{m}(-x)}{Q_{m+1}(x)}=F_{m}(x).

In the computation above, the properties (2) and (3) of the Theorem3 were used. ∎

4 Concluding Remarks

As we mentioned earlier, Xin and Zhong([4]) analyzed the generating function Gn​(y)=∑m≥0b​(n,m)​ymG_{n}(y)=\sum_{m\geq 0}b(n,m)y^{m} in detail. It is an Ehrhart series of graph polytope for the linear graph which is the rational function of the form

Gn​(y)=Hn​(y)(1−y)n+1,G_{n}(y)=\frac{H_{n}(y)}{(1-y)^{n+1}},

where Hn​(y)H_{n}(y) is a polynomial of degree at most n.n. Consider

K​(x,y)=∑n≥0Gn​(y)​xn=∑m≥0Fm​(x)​ym.K(x,y)=\sum_{n\geq 0}G_{n}(y)x^{n}=\sum_{m\geq 0}F_{m}(x)y^{m}.

Our question is the following: what is the form of the generating function K​(x,y)K(x,y) exactly?

This bi-variate generating function K​(x,y)K(x,y) requires more analysis and understanding of us.

References

  • [1] S. J. Cyvin and I. Gutman, Kekulé Structures in Benzenoids Hydrocarbons, Lecture Notes in Chemistry, Vol.46, Springer, New York, pp.142-144, 1988.
  • [2] H.-K. Ju, On the Sequence Generated by a Certain Type of Matrices. Honam Math. J. Vol.39, No.4, pp.665-675, 2017.
  • [3] The On-Line Encyclopedia of Integer Sequences.
  • [4] G. Xin and Y. Zhong, Proving Some Conjectures on Kekulé Numbers for Certain Benzenoids by Using Chebyshev Polynomials. Advances in Applied Math. Vol.415, 2023.