Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

3 Answers

up vote 5 down vote accepted

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

share|improve this answer
    
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
add comment

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 $

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.