# A binet-like formula for $\small 1 , 2 , 3 , 6 , 9 , 18 , 27, 54, 81, \ldots$?

This is more a "recreational" problem. By another question I came to the question for a closed-form-formula for this sequence $\small 1 , 2 , 3 , 6 , 9 , 18 , 27, \ldots$ which is just the mixture of the sequences $\small 3^k$ and $\small 2 \cdot 3^k$ .

I tried to find the "Binet"-type expression for it (like for instance for the Fibonacci-sequence) but do not find the initial "key". What is the way to such a formula?

-
Are you looking for a Binet-type recurrence equation? I cannot make out what "expression" or "formula" means in your question. (Perhaps you could explain the term with an example.) –  Srivatsan Jan 11 '12 at 17:14
Oh, mixture means interleaving. I though it meant linear combination, in which case one would expect a Binet-like formula from a recurrence equation. –  lhf Jan 11 '12 at 18:11
@Srivatsan: "Binet" like in the wikipedia for the fibonacci-sequence, where the "Binet"-form has the index for the sequence in the exponents of a sum (and may so be interpolated, for instance) and allows the computation of the single terms of the sequence by some closed-form expression only involving two exponentials. Joriki has given a satisfying answer, so I think there is no more need to extend the question? –  Gottfried Helms Jan 11 '12 at 18:31
@lhf: yes: "interleaving" was the english word which I couldn't remember, sorry (I thought "intervowen" and "interwoven" but couldn't decide which was the correct/nearest one and gave up. "mixed" resp "mixture" was then my last choice... ;-)) –  Gottfried Helms Jan 11 '12 at 18:34

Substituting the values $a_0=1$ and $a_1=2$ into the ansatz $a_k=c_1\sqrt3^k+c_2(-\sqrt3)^k$ yields

$$\begin{eqnarray} c_1+c_2&=&1\;,\\ c_1-c_2&=&2/\sqrt3\;, \end{eqnarray}$$

which gives $c_1=(1+2/\sqrt3)/2$ and $c_2=(1-2/\sqrt3)/2$ and thus

$$\begin{eqnarray} a_k&=&\frac{(1+2/\sqrt3)\sqrt3^k+(1-2/\sqrt3)(-\sqrt3)^k}2\\ &=&\frac{\sqrt3^k+(-\sqrt3)^k}2+\sqrt3^{k-1}+(-\sqrt3)^{k-1}\;.\\ \end{eqnarray}$$

The factors $\sqrt3$ and $-\sqrt3$ can either be guessed or derived from the recurrence relation $a_{k+2}=3a_k$, which leads to the characteristic equation $\lambda^2=3$.

-
Thanks, that's a good help. However, I see I've to try harder to understand that mechanism in general. Because the growth rate of the sequence was q=3 for two steps I already tried with a similar $\small \sqrt3$-formula but without arriving at the correct one. Hmmm... –  Gottfried Helms Jan 11 '12 at 18:37
ahh, and I could use this to solve now the same problem where the analogue sequence begins with $\small 4,5,12,15,35,45,\ldots$. Now the true original problem (of which this was only a part) remains.... ;-) –  Gottfried Helms Jan 11 '12 at 19:05
@Gottfried: I think you mean $36$ instead of $35$? –  joriki Jan 11 '12 at 19:39
true, mistyped. (and cannot be edited 42 minutes later) –  Gottfried Helms Jan 11 '12 at 19:48

A natural approach employs geometric generating functions and partial fraction decomposition.

$$\rm\frac{1}{1-3\ x^2}\ =\ 1 + 3\ x^2 + 9\ x^4+\ \cdots$$

$$\rm\ \ \ \frac{2\ x}{1-3\ x^2}\ =\ 2\ x + 6\ x^3 + 18\ x^5+\ \cdots$$

So your sought intermingled sequence $\rm\:f_n\:$ has generating function being their sum

$$\rm \frac{1+2\ x}{1-3\ x^2}\ =\ \frac{1/2 + 1/\alpha}{1-\alpha\ x}\ +\ \frac{1/2-1/\alpha}{1+\alpha\ x},\quad\ \alpha = \sqrt{3}$$

Thus, comparing coefficients $\rm\ \ f_n\ =\ (1/2 + 1/\alpha)\ \alpha^n\ +\ (1/2 - 1/\alpha)\ (-\alpha)^n$

-
Well, this is an even more elegant looking exposition. I'll see with which I can work more naturally. Thanks, too! –  Gottfried Helms Jan 11 '12 at 19:11

This is sequence A038754 in the On-Line Encyclopedia of Integer Sequences.

-
arrghh... I didn't even think of the OEIS, because that sequence seemed so simple. Thanks for the hint - there is more valuable information there. –  Gottfried Helms Jan 11 '12 at 18:42