3

Array $a_n$ is defined as:

$$a_0 = 1, \quad a_{n+1} = k_{a1}a_{n} + k_{a0}$$

Array $b_n$ is defined as:

$$b_0 = 1, \quad b_{n+1} = k_{b1}b_{n} + k_{b0}$$

Array $c_n$ is defined as:

$$c_n = a_{n}b_{n}$$

($k_{a1}$, $k_{a0}$, $k_{b1}$, $k_{b0}$ are some constants)

I suspect (but may be wrong) that $c_n$ would have to satisfy a linear recurrent relation involving only elements of itself, but of higher degree than recurrences for $a_n$ and $b_n$. Is it possible to derive such recurrent relation in this (or similar) form:

$$c_0 = 1, c_1 = (k_{a1}+k_{a0})(k_{b1}+k_{b0}), \quad c_{n+2} = k_{c2}c_{n+1} + k_{c1}c_{n} + k_{c0}$$

with $k_{c2}$, $k_{c1}$, $k_{c0}$ expressed as functions of $k_{a1}$, $k_{a0}$, $k_{b1}$, $k_{b0}$?

Or, maybe I am wrong, and such recurrence relation does not exist?

VividD
  • 15,966
  • Got something from an answer? – Did Jan 10 '15 at 18:42
  • Sure, @Did, the research/investigation is going on... Interesting area of math... I am hoping perhaps someone else will chime in with another idea, that's why for now I keep your answer unmarked, if you wonder about that... – VividD Jan 10 '15 at 18:51
  • OK, let me be more specific: did you check the formula I suggested? – Did Jan 10 '15 at 18:54
  • @Did I don't think the formula is right (for case $u=v=1$, it follows $c_n=n^2$, and it looks the formula doesn't yield the right recurrence), but the idea is good, to restrict general case, and get reasonable formulas. – VividD Jan 10 '15 at 19:16
  • Funny: if $u=v=1$, the formula in my post works like a charm. – Did Jan 10 '15 at 19:19
  • It works, now I see, I made a mistake! – VividD Jan 10 '15 at 19:36
  • So... where does this leave us? Did you try to adapt the formula in my answer to the case $a\to ua+r$, $b\to vb+s$? – Did Jan 10 '15 at 19:39
  • No, @Did, i did not. It looks too difficult for me. Sorry for slow response, I am here busy with something unrelated. – VividD Jan 10 '15 at 19:58
  • Sorry but I fail to see the difficulty: assume $a\to ua+r$, $b\to vb+s$ and compute $(A,B,C,D)$ such that $c_{n+3}=Ac_{n+2}+Bc_{n+1}+Cc_n+D$. And if you want to be clever, consider $\bar a=a/r$, $\bar b=b/s$ and $\bar c=\bar a\bar b$... – Did Jan 10 '15 at 21:24

2 Answers2

2

Recursions of degree $3$ are necessary (and probably sufficient), for example, if $$a_0=b_0=1,\qquad a_{n+1}=ua_n+1,\qquad b_{n+1}=vb_n+1,$$ then (I believe that) the sequence $c_n=a_nb_n$ solves the recursion $$ c_{n+3}=(uv+u+v)c_{n+2}-uv(u+v+1)c_{n+1}+u^2v^2c_n+1-uv.$$

Did
  • 279,727
1

Use generating functions, define $A(z) = \sum_{n \ge 0} a_n z^n$ and similarly $B(z)$. Multiply your recurrences by $z^n$ and add over $n \ge 0$, recognize e.g. $\sum_{n \ge 0} a_{n + 1} z^n = (A(z) - a_0)/z$ and get:

$\begin{align} \frac{A(z) - 1}{z} &= k_{a 1} A(z) + \frac{k_{a 2}}{1 - z} \\ \frac{B(z) - 1}{z} &= k_{b 1} B(z) + \frac{k_{b 2}}{1 - z} \end{align}$

Solutions are:

$\begin{align} A(z) &= \frac{1 + (k_{a 2} - 1) z}{1 - (k_{a 1} + 1) z + k_{a 1} z^2} \\ B(z) &= \frac{1 + (k_{b 2} - 1) z}{1 - (k_{b 1} + 1) z + k_{b 1} z^2} \end{align}$

Splitting into partial fractions allows to get the terms $a_n$ and $b_n$ from the resulting geometric series, either in the form $a_n = r_{a 1} \alpha_a^n + r_{a 2} \beta_a^n$ (denominator has different zeros) or $a_n = s_{a 1} \alpha_a^n + s_{a 2} n \alpha_a^n$ (denominator is a square), similarly for $b_n$. In any case, your $c_n = a_n b_n$ will be the product of the above. Assuming all zeros of the denominators distinct, you have something like:

$$ c_n = r_{c 1} (\alpha_a \alpha_b)^n + r_{c 2} (\alpha_a \beta_b)^n + r_{c 3} (\beta_a \alpha_b)^n + r_{c 4} (\beta_a \beta_b)^n $$

(If zeros repeat in a denominator, change e.g. $\beta_a \mapsto n \alpha_a$; if zeros repeat among denominators you get less terms). This is the solution to a homogeneous linear recurrence of order (at most) 4 with constant coefficients. Using the same process as above backwards you can derive this recurrence. Yes, it is a mess.

vonbrand
  • 27,812