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
    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.)2012-01-11
  • 0
    Oh, *mixture* means *interleaving*. I though it meant *linear combination*, in which case one would expect a Binet-like formula from a recurrence equation.2012-01-11
  • 0
    @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?2012-01-11
  • 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
    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...2012-01-11
  • 0
    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.... ;-)2012-01-11
  • 0
    @Gottfried: I think you mean $36$ instead of $35$?2012-01-11
  • 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