3

In this question, I’ll temporarily bypass MSE rules and wait a little bit before revealing the context, because I believe people looking at it with a fresh eye will be able to see several things that I'm unable to see now.

I’ve computed the six first terms of a sequence that looks fairly regular :

$$ \begin{eqnarray} u_1 &=& (3,3,2) \\ u_2 &=& (15,24,41) \\ u_3 &=& (57,45,122) \\ u_4 &=& (213,336,1247) \\ u_5 &=& (795,627,2954) \\ u_6 &=& (2967,4680,26729) \end{eqnarray} $$

The coefficients seem to grow sort of exponentially. Can anybody guess a closed form, or an induction rule for $u_n$ ?

UPDATE 06/01/2013 : Abel’s enlightening comments below allowed me to improve my algorithm and compute some more values, up to the 16th value.

Those values confirm the guesses about the linear recurrence relations guessed by Abel for the first and second coordinate.

For the third coordinate, one obtains the following sequence :

$$ 2, 41, 122, 1247, 2954, 26729, 58610, 502655, 1059602, 8816873, 18146666, 148093919, 299943578, 2414936489, 4834990562, 38541995519 $$

One can check that this $16$-element sequence does not satisfy any linear recurrence of order $8$. Does anybody see a pattern here ?

Ewan Delanoy
  • 61,600
  • Well I immediately notice that the first and second term are divisible by three for each $u_i$. – Dan Rust May 26 '13 at 14:56
  • 1
    For the first component we seem to have $n_{i+2} = 4n_{i+1}-n_i$. – Abel May 26 '13 at 14:56
  • @Abel Nice! You’re the best observer so far. – Ewan Delanoy May 26 '13 at 14:59
  • 2
    For the second components we have something like $45 = 2\cdot 24-3$, $336 = 8\cdot 45-24$, $627=2\cdot 336-45$, $4680 = 8\cdot 627-336$ etc. I'm guessing the rule is $n_{i+2} = 2n_{i+1}-n_i$ for odd $n$ and $n_{i+2} = 8n_{i+1}-n_i$ for even $n$. It's getting uglier :). – Abel May 26 '13 at 15:11
  • As for the third component: I currently have the impression that for even $i$, $n_i = (2i-1)k_i-2\cdot n_{i-1}$, where $n$ denotes the third component and $k$ denotes the first component. For odd $i$ I still have no idea as of yet. I'll sleep on it. – Abel May 27 '13 at 00:33

1 Answers1

0

For the first component at least, the recursion $n_{i+2} = 4n_{i+1}-n_i$ by Abel leads to the differential equation $f''(x) = 4f'(x) - f(x)$, which gives the exponential generating function:

$c_1e^{-(\sqrt{3} - 2)x} + c_2e^{(2 +\sqrt{3})x}$

The initial conditions $n_0$ = 3 and $n_1$ = 15 give the values

$c_1 = \frac{3}{2} - \frac{3\sqrt{3}}{2}$ and $c_2 =\frac{3}{2} + \frac{3\sqrt{3}}{2}$.

So the terms in the sequence are simply the coefficients of $\frac{x^n}{n!}$ in the series expansion of $c_1e^{-(\sqrt{3} - 2)x} + c_2e^{(2 +\sqrt{3})x}$, which should just be:

$c_1(2 -\sqrt{3})^n + c_2(2 + \sqrt{3})^n$.

MattyZ
  • 2,313