2
$\begingroup$

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?

  • 0
    @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... ;-))2012-01-11

3 Answers 3

5

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$.

  • 0
    true, mistyped. (and cannot be edited 42 minutes later)2012-01-11
5

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 $

  • 0
    Well, this is an even more elegant looking exposition. I'll see with which I can work more naturally. Thanks, too!2012-01-11
4

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

  • 0
    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.2012-01-11