The Hadamard product and recursively defined sequences

1. Introduction

Let us begin with some notation. Let \( {b}\) be a row vector and \({a}\) be a finite row vector; \(({b})_j\) denotes \(j\)th element of vector \({b}\), \(|{b}|\) denotes length of \( {b}\); \({a} ◡ {b} ≝\left( ({a})_1 ,\ldots , ({a})_{|{a}|} \ , ({b})_1 , \ldots \right) \), \(({b})_{l}^{m} ≝\left( ({b})_j \right) _{j=l}^{m}\), \(|{b}|_x ≝ \sum_{j=1}^{|{b}|} ({b})_j x^{j-1}\), \({1}_{m} ≝\left( 1 \right)_{j=1}^{m}\), \({0}_{m} ≝\left( 0 \right)_{j=1}^{m}\), \([ l, m ]_j ≝ ({{1}}_\infty \times ( {{0}}_{l} ◡ {{1}}_{m} ) )_j\), where \(\times\) denotes the Kronecker product, \( l \in \mathbb{N}\), \(m \in \mathbb{N} \cup \{\infty\}\). Note that the last function can be expressed by the ceiling function: \([ l, m ]_j = \lceil (j + m)/(l + m)\rceil – \lceil j/(l + m)\rceil\).

Also, we use ordinary notation to denote the corresponding entrywise operations. For example, \({a}^2\) expresses the Hadamard square: \({a}^2 =\left( {({a})_j}^2 \right) _{j=1}^{|{a}|}\).

It should be noted that there are many papers on sequences generated by linear difference equations with variable coefficients. See, for examle, [1], [2], [3]. The simple approach illustrated here involves constructing for each such sequence a corresponding recursive vector sequence, which can be explicitly expressed using the following property of Hadamard product: \(({a}{c})\ast ({b}{d})=({a} \ast {b})({c} \ast {d})\), where \(|{c}| = |{a}|\), \(|{d}| = |{b}|\) and \(\ast \in \{ ◡ , \times \}\).

2. Linear recurrences

First we use this property with respect to concatenation.

Theorem 1. If \(x_1\), \(x_2\) are arbitrary numbers, \(a_n\), \(b_n\) are arbitrary number sequences and \(x_n = a_n x_{n-1} + b_n x_{n-2}\) for \(n\geqslant 3\), then $$ x_n = \sum_{j=1}^{f_n} ((x_1 – x_2)({f})_j + x_2) \biggl( \prod_{\substack{3 \leqslant k \leqslant n \\ ({f}_k)_j = 1}} b_k \biggr) \biggl( \prod_{\substack{3 \leqslant k \leqslant n \\ ({f}_k + {f}_{k+1})_j = 0}} a_k \biggr) \text{,} $$ where \(f_n\) is \(n\)th Fibonacci number, \({f} =\left( 0,1,0,0,\ldots \right) \) is infinite Fibonacci word; \({f}_k\) is obtained from \({f}\) by replacing each entry of zero with \(f_{k-1}\) zeros and each entry of one with \(f_{k-2}\) ones.

Proof. Define vectors: \({x}_1 =\left( x_1 \right)\), \({x}_2 =\left( x_2 \right)\), \({x}_n = (b_n {x}_{n-2}) ◡ (a_n {x}_{n-1})\) for \(n\geqslant 3\) and \({y}_1 = {x}_1\), \({y}_n = {y}_{n-1} ◡ {x}_n\), \({p}_n = {1}_{f_{n+1}-1} ◡ (b_n {1}_{f_{n-2}}) ◡ (a_n {1}_{f_{n-1}}) \) for \(n\geqslant 2\).
Let \(\Lambda_k {b} ≝ {b} ◡ ({b})_k^{|{b}|}\). We have \({y}_n = {p}_n \Lambda_{f_{n-1}} {y}_{n-1}\) for \(n\geqslant 3\), from which it follows that \({y}_n = {y}_{2,n} \prod_{k=3}^n{p}_{k,n}\), where \({y}_{2,n} = \Lambda_{f_{n-1}}\Lambda_{f_{n-2}}\ldots\Lambda_{f_2}{y}_2\), \({p}_{k,n} = \Lambda_{f_{n-1}}\Lambda_{f_{n-2}}\ldots\Lambda_{f_k}{p}_k\).
Partition \({y}_{2,n} = {y}_1′ ◡ \ldots ◡ {y}_n’\) such that \(|{y}_i’| = f_i\), then \({y}_1′ = {x}_1\), \({y}_2′ = {x}_2\), \({y}_n’ = {y}_{n-2}’ + {y}_{n-1}’\) for \(n\geqslant 3\). Similarly partition \({p}_{k,n} = {p}_{k,1}’ ◡ \ldots ◡ {p}_{k,n}’\) such that \(|{p}_{k,i}’| = f_i\), then \({p}_{k,i}’={1}_{f_i}\) for \(1 \leqslant i\leqslant k-1\), \({p}_{k,k}’=(b_k {1}_{f_{k-2}}) ◡ (a_k {1}_{f_{k-1}})\), \({p}_{k,i}’ = {p}_{k,i-2}’◡ {p}_{k,i-1}’\) for \(k+1 \leqslant i\leqslant n\).
Note that \(({x}_n)_{-} = ({y}_n’)_{-} \prod_{k=3}^n({p}_{k,n}’)_{-}\), where by \(({a})_{-}\) we denote the vector composed of elements of \({a}\) in reverse order. Now \(({y}_n’)_{-}\) and \(({p}_{k,n}’)_{-}\) can be expressed in terms of infinite generalized Fibonacci words: \(({y}_n’)_{-} = (x_1 – x_2) ( {f} )_1^{f_n} + x_2 {1}_{f_n}\), \(({p}_{k,n}’)_{-} = ( {f}_{k+1} + b_k {f}_k + a_k ({1}_{f_n}-{f}_{k+1}-{f}_k))_1^{f_n}\). Finally using \(x_n = |({x}_n)_{-}|_1\) we get the result.

Remark 1. It is easy to check that the result of Theorem 1 can be reformulated as follows:

The same sequence can be expressed with help of the Kronecker product.

Theorem 2. If \(x_1\), \(x_2\) are arbitrary numbers, \(a_n\), \(b_n\) are arbitrary number sequences and \(x_n = a_n x_{n-1} + b_n x_{n-2}\) for \(n\geqslant 3\), then $$ x_n = \sum_{\substack{2^{n-2} + 1 \leqslant j \leqslant 2^{n-1} \\ \vartheta(2^{n-1}-j+1)= 1} } ((x_2-x_1)[ 1,1 ]_j + x_1) \prod_{\substack{0 \leqslant k \leqslant n-3 \\ [ 3\cdot2^k,2^k ]_j =1 }}a_{k+3} \prod_{\substack{0 \leqslant k \leqslant n-3 \\ [ 2^k,2^k ]_j =0 }}b_{k+3} \text{,} $$ where \(\vartheta (n) ≝ \prod_{k=0}^{\infty} (1-[ 3\cdot2^k,2^k ]_n)\).

Proof. Define vectors: \({r}_1 =\left( x_1 , x_2 \right)\), \({r}_n = ({1}_2 \times {r}_{n-1})({h}_n \times {1}_{2^{n-2}})\) for \(n\geqslant 2\), where \({h}_n =\left( 0,1,b_{n+1},a_{n+1}\right)\). It can be easily shown that \(|({r}_n)_{2^{n-1}+1}^{2^n}|_1 = x_{n+1}\). Solving the recurrence equation we get: \(r_n = ({1}_{2^{n-1}} \times {r}_1) \prod_{k=2}^{n} ({1}_{2^{n-k}} \times {h}_k \times {1}_{2^{k-2}})\). Taking into account that \({h}_k =\left( 0,1,1,1 \right)\left( b_{k+1},1,b_{k+1},1\right)\left( 1,1,1, a_{k+1}\right) \) and doing some calculations we get the result.

The following lemma allows us to generalize the result to the nonhomogeneous case.

Lemma 1. If \({x}_1\) is arbitrary vector, \({b}_n\) is \(0,1\)-vector sequence, \({a}_n\) and \({c}_n\) are such that \(|{a}_n| = |{c}_n| = |{x}_1| \prod_{i=2}^n |{b}_i|\); \({x}_n = {a}_n ({b}_n \times {x}_{n-1})+{c}_n\) for \(n \geqslant 2\), then $$ {x}_n=({b}_{n,2} \times {x}_1) \prod_{k=2}^n({b}_{n,k+1} \times {a}_k) + \sum_{i=2}^n({b}_{n,i+1} \times {c}_i)\prod_{k=i+1}^n({b}_{n,k+1} \times {a}_k) \text{,} $$ where \({b}_{n,k} = {b}_n \times {b}_{n-1} \times \cdots \times {b}_k\), if \(k\leqslant n\) and \({b}_{n,k} = {1}_1\), if \(k > n\).

The proof is straightforward. Vectors \({r}_n’\) for similar nonhomogeneous sequence \(x_n’ = a_n x_{n-1}’ + b_n x_{n-2}’ + c_n\) such that \(|({r}_n’)_{2^{n-1}+1}^{2^n}|_1 = x_{n+1}’\), are defined as follows: \({r}_1′ =\left( x_1 , x_2 \right)\), \({r}_n’ = ({1}_2 \times {r}_{n-1}’)({h}_n \times {1}_{2^{n-2}}) + c_n ( {0}_{2^n-1} ◡ {1}_1 )\) for \(n\geqslant 2\). To use the lemma we should, of course, do substitutions \({a}_n={h}_n \times {1}_{2^{n-2}}\) and \({b}_{n,k} = {1}_{2^{n-k+1}}\).

Theorem 3. If \(w_0\) is arbitrary number, \(a_{n,j}\) is arbitrary number sequence and \(w_n = \sum_{j=0}^{n-1}a_{n,j}w_j\) for \(n\in \mathbb{N}\), then $$ \sum_{j=0}^nw_j = w_0 \sum_{{v}\in \mathbb{V}_n}\prod_{k=1}^{|{v}|}a_{({v})_k , ({0}_1 ◡ {v})_k }\text{,} $$ where set \(\mathbb{V}_n\) consists of all vectors \({v}\) such that \(1 \leqslant({v})_{i-1} < ({v})_i \leqslant n\) for \(2 \leqslant i \leqslant |{v}|\).

Proof. Define vectors: \({w}_0 =\left( w_0 \right)\), \({w}_1 =\left( w_0 , a_{1,0} w_0 \right)\), \({w}_n = {w}_{n-1} ◡ ({w}_{n-1} {q}_n)\) for \(n\geqslant 2\), where \(({q}_n)_1 = a_{n,0}\), \(({q}_n)_{2^{k-1}+1}^{2^k} = a_{n,k} {1}_{2^{k-1}}\) for \(1 \leqslant k\leqslant n-1\). From the recurrence equation it follows that if equality \(|{w}_l|_1 = \sum_{j=0}^l w_j\) is true for \(l=n-1\geqslant 1\), then it is true for \(l=n\); it is true for \(l=1\), so we conclude that it is true for any \(l \in \mathbb{N}\). Solving the recurrence equation, we get: \({w}_n = w_0 \prod_{k=1}^n ({1}_{2^{n-k}} \times ({1}_{2^{k-1}} ◡ {q}_k)) \) for \(n \in \mathbb{N} \). Noting that \({q}_k =\left( a_{k,\lceil \log_2 j\rceil} \right)_{j=1}^{2^{k-1}}\) we have $$ |{w}_n|_1 = w_0 \sum_{j=1}^{2^n}\prod_{k=1}^n([2^{k-1},2^{k-1}]_j (a_{k,\lceil \log_2 ( 1+ (j-1)\bmod2^{k-1})\rceil} -1) +1) \text{.} $$ The quantity \([2^k,2^k]_j\) equals the value of \(k\)th digit of number \((j-1)\) in binary numeral system. If \(k_i\) is serial number of \(i\)th digit \(1\), then \(\lceil \log_2 (1+{(j-1)\bmod 2^{k_i}})\rceil = 1+k_{i-1}\). Therefore, \(|{w}_n|_1 = w_0 \sum_{j}\prod_{i}a_{k_i + 1,k_{i-1}+1}\), assuming \(k_{0}=-1\). Here \((k_i +1)\) ranges over \({v} \in \mathbb{V}_n\): \(k_i +1 = ({v})_i\).

In the same way vectors \({w}_n’\) for nonhomogeneous sequence \(w_n’ = c_n + \sum_{j=0}^{n-1}a_{n,j}w_j’\) such that \(|{w}_l’|_1 = \sum_{j=0}^l w_j\), are defined as follows: \({w}_0′ =\left( w_0 \right)\), \({w}_1′ =\left( w_0 , c_1 + a_{1,0} w_0 \right)\), \({w}_n’ = {w}_{n-1}’ ◡ ({w}_{n-1}’ {q}_n) + c_n ({0}_{2^n-1} ◡ {1}_1) \) for \(n\geqslant2\).

3. Quadratic map

It is well-known that in many cases iterations of a polynomial of degree 2 in the general case, i.e. solutions of quadratic map, can be expressed by iterations of a polynomial of degree 2 with one parameter.

Theorem 4. Let \(p^{(0)}(x)=x\), \(p^{(n)}(x)=p^{(n-1)}(p(x))\) \((\) for \(n \in \mathbb{N}\) \()\) be iterations of polynomial \(p(x)=\lambda (x+1)x\), then $$ p^{(n)}(x)=\sum_{k=1}^{2^n}x^k\sum_{i=(k-1)\omega_n}^{k \omega_n -1} \prod_{j=1}^n \lambda ^{\mu_{i,j-1}}\binom{\mu_{i,j-1}}{\mu_{i,j} – \mu_{i,j-1}}\text{,} $$ where \(\omega_n = 2^{\frac{n(n-1)}{2}}\), \(\mu_{i,j} = \lceil \frac{1+ i \bmod \omega_{j+1}}{\omega_j} \rceil\).

Proof. Any polynomial \(p^{(n)}(x)\) can be expressed as follows: \(p^{(n)}(x) = \sum_{k=1}^{2^n} g_{n,k}x^k\), where \(g_{n,k}=g_{n,k}(\lambda)\) are polynomials defined by equalities: \(g_{0,1}=1\), \(g_{n,k}=\sum_{i=1}^{2^{n-1}}q_{k,i} g_{n-1,i}\) (for \( 1 \leqslant k \leqslant2^n\)), where \(q_{k,i}=\lambda^i \binom{i}{k-i}\). Let \({p}_0 =\left( 1 \right)\), \({p}_n = ({1}_{2^n} \times {p}_{n-1}) ({q}_n \times {1}_{\omega_{n-1}})\) for \(\in \mathbb{N}\), where $${q}_n = (q_{1,j})_{j=1}^{2^{n-1}} ◡ (q_{2,j})_{j=1}^{2^{n-1}} ◡ \ldots ◡ (q_{2^n,j})_{j=1}^{2^{n-1}} =\left( q_{\lceil i/2^{n-1}\rceil, 1+ (i-1)\bmod 2^{n-1} }\right)_{i=1}^{2^{2n-1}} \text{.} $$ Then \(|({p}_n)_{1+(k-1)\omega_n}^{k\omega_n}|_1 = g_{n,k}\). Solving the equation, we get: $$ {p}_n = \prod_{k=1}^n \biggl( {1}_{2^{\frac{(n+k+1)(n-k)}{2}}} \times {q}_k \times {1}_{\omega_{k-1}} \biggr) \text{.} $$ The last step is to check that \({1}_{\infty} \times {q}_k \times {1}_{\omega_{k-1}} =\left( {q}_{\mu_{j,k},\mu_{j,k-1}} \right)_{j=0}^{\infty} \).

Remark 2. Using generating polynomial \(|{q}_k|_t=\lambda(1+t^m) ((\lambda t^{m+1} + \lambda t^{2m+1})^m -1)/(\lambda t^{m+1} + \lambda t^{2m+1}-1)\), where \(m=2^{k-1}\) and taking in account formula \(|{a} \times {b}|_t =|{a}|_{t^{|{b}|}} |{b}|_t\) we can represent \(p^{(n)}(x)\) as Hadamard’s product of \(n\) functions. The polynomial \(|{q}_k|_t\) can be derived using polynomials \(\varphi_{k,m} = \sum_{j=1}^m \binom{j}{k-j} (\lambda t)^{j-1}\) as follows. Taking in account that \(\varphi_{k,m} = \lambda t (\varphi_{k-1,m}+\varphi_{k-2,m})-(\lambda t)^m \binom{m+1}{k-m-1}\) for \(k \geqslant 3\) and \(m \geqslant 1\), we can write \begin{align} \lambda^{-1} |{q}_k|_t & = \sum_{k=1}^{2 m}t^{(k-1)m}\varphi_{k,m} \notag = 1+t^m + \lambda t^{m+1}\sum_{k=1}^{2m-1}t^{(k-1)m}\varphi_{k,m} + \lambda t^{2 m+1}\sum_{k=1}^{2m-2}t^{(k-1)m}\varphi_{k,m} -\lambda^m \sum_{k=2}^{2m}t^{k m}\binom{m+1}{k-m-1}\notag \\ & = 1+t^m + \lambda t^{m+1}(\lambda^{-1}|{q}_k|_t – t^{m(2m-1)}\varphi_{2m,m}) + \lambda t^{2 m+1}(\lambda^{-1}|{q}_k|_t – t^{m(2m-1)}\varphi_{2m,m}- t^{m(2m-2)}\varphi_{2m-1,m} ) \notag \\ & -\lambda^m (t^{m(m+1)}(1+t^m)^{m+1}-(m+t^m+1)t^{2 m^2 +m}). \notag \end{align} From here taking in account \(\varphi_{2m,m}=(\lambda t)^{m-1}\) and \(\varphi_{2m-1,m}=m (\lambda t)^{m-1}\) we immediately get \(|{q}_k|_t\).

Let’s consider another episode. Let \(s^{(0)}(x)=x\), \(s^{(n)}(x)=s^{(n-1)}(s(x))\) (for \(n \in \mathbb{N} \)) be iterations of polynomial \(s(x)= s_\lambda(x)=\lambda (x^2-1)+1\) and \(\lambda \neq 0\). Define vectors: \({s}_1 =\left( x-1, 1\right)\), \({s}_n = \lambda {s}_{n-1}^{\langle 2 \rangle} – (\lambda -1) ({0}_{2^{2^{n-1}}-1} ◡ {1})\) for \(n \geqslant 2\), where triangular brackets indicate Kronecker degree. Obviously, \(|{s}_n|_1 = s(|{s}_{n-1}|_1) = s^{(n)}(x)\). Solving the equation, we get: where \({l}_n = {1}_{2^{2^n}-1} ◡\left( \lambda^{-1} \right)\), \({r}_{\lambda,n} = \prod_{i=1}^{n}{l}_i^{\langle 2^{n-i}\rangle}\), \({r_\lambda} = \prod_{i=1}^{\infty}{l}_i^{\langle \infty \rangle}\). Therefore, we have where \({h}_n = \log_2\bv 2,1 \right)^{\langle 2^{n-1} \rangle}\). And it can be easily shown that $$({h}_n)_j = 2^{n-1}-\sum_{k=0}^{\infty}[2^k,2^k]_j \text{ and } (\log_2 {r}_{2,n})_j = \sum_{k,i=0}^{\infty}[2^{2^i k}(2^{2^i}-1),2^{2^i k}]_j $$ by using simple formula $$(\log_2 ({1}_{m-1} ◡\left( 2 \right))^{\langle n \rangle})_j = \sum_{k=0}^{n-1}[m^k(m-1),m^k]_j \text{ (for } j\leqslant m^n \text{).} $$ Substituting \(2\) for \(x\) in (2), we have $$ s_\lambda^{(n)} (2) = \lambda^{2^{n-1}-1}\sum_{k=1}^{2^{n-1}}\kappa_{n,k}{\lambda}^{-k}\text{,} $$ where \(\kappa_{n,k}\) denotes the number of elements in \(\log_2 {r}_{2,n-1}\) that equal to \(k\). This function can be defined recursively as follows: $$\kappa_{n,0} = 3^{2^{n-1}} , \kappa_{1,k} = \delta_{k,1} , \kappa_{n,k} =\delta_{k,2^{n-1}} – \delta_{k,2^{n-2}} + \sum_{i=0}^k \kappa_{n-1,k-i} \kappa_{n-1,i} \text{.} $$ Evaluating \(\kappa_{n,k}\) we have: $$\kappa_{n,1} = 2^{n-1} 3^{2^{n-1}-1}, \kappa_{n,2} = -\kappa_{n,1} (\frac{1}{12}-\sum_{i=0}^{n-1}\kappa_{i+1,1}({\kappa_{i,1}}^2 + \delta_{k,2^{n-1}} – \delta_{k,2^{n-2}}) $$ and so on.

Remark 3. Replacing \(2^{n-1}\) by \(n\) in the last expression of (1), we get new sequence of vectors: \({s}_n’ = \lambda^{n-1} {s}_1^{\langle n \rangle} ({r})_1^{2^n}\). Let \(f_n(x) = |{s}_n’|_1\). Conjecture: $$ f_n(x)= \begin{cases} f_{n/2}(s(x)) \text{, if } n \text{ is even} \\ \lambda x f_{n-1}(x) \text{, if } n \text{ is odd}\\ x \text{, if } n=1. \end{cases} $$

Author Contributions

All authors contributed equally to the writing of this paper. All authors read and approved the final manuscript.

Conflicts of Interest:

The authors declare no conflict of interest.