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.

I am self-studying Discrete Mathematics, and I have two exercises to solve.

Find a formula for the following recurrence relation: (translated from Portuguese)

a) $a_{1}=3,a_{2}=5, a_{n+1}=3a_{n}-2a_{n-1}.$

b) $a_{1}=1,a_{2}=3, a_{n+2}=a_{n+1}+a_{n}.$

Let me show how I solved the first one. Note that $a_{1}=3,a_{2}=5, a_{3}=9,a_{4}=17$, then $a_{n}=2^{n}+1$ for all $n\in \mathbb{N}$ (I proved it by induction on $n$), but the last one I was not able to solve.

I would appreciate your help.

share|improve this question
    
Go look up "Lucas Numbers", a sequence starting with $1,3$ and $a_{n+2} = a_n+a_{n+1}$ looks like Lucas Numbers –  Jeremy Carlos Mar 16 '12 at 20:30
    
Did you prove your attempt for a)? –  Raphael Mar 16 '12 at 20:39
    
@Raphael: Yes! By induction on $n$. –  spohreis Mar 16 '12 at 20:57
    
i think the answer is $ \frac{\alpha^{2n+2}-\beta^{2n+2}}{\sqrt5} $ where $\alpha $ and $\beta $ you can get from Andre Nicolas's suggestion. –  Lorenz Chaos Mar 16 '12 at 21:09
add comment

5 Answers 5

up vote 9 down vote accepted

There is a standard method which is sketched below. Forget about the initial conditions $a_1=1$, $a_2=3$ for now. We look for solutions of the recurrence relation of the shape $a_n=x^n$, where $x$ is a number to be determined.

Substituting in the recurrence, we get $x^{n+2}=x^{n+1} +x^n$. Forgetting about the possibility $x=0$, which mostly can't happen, this reduces to $x^2-x-1=0$. Solve. We get $$x=\frac{1\pm\sqrt{5}}{2}.$$ Call the two roots $\alpha$ and $\beta$. (The number $\frac{1+\sqrt{5}}{2}$ is a famous number, often called the Golden Number. It even has two standard symbols attached to it, $\varphi$ and $\tau$.)

Now look for numbers $A$ and $B$ such that the expression $A\alpha^n+B\beta^n$ satisfies your initial conditions. (If you have studied Differential Equations, the procedure will be structurally familiar, for good reason.)

The suitable $A$ and $B$ are not hard to find. We get $A=B=1$. To check that $a_n=\alpha^n +\beta^n$ is indeed the solution, note that $A\alpha^n+B\beta^n$ satisfies our recurrence for any $A$ and $B$. Choosing $A$ and $B$ so that the initial conditions are satisfied forces the formula to be correct for all $n$.

It would have been a little more pleasant to find $A$ and $B$ if we had been given the usual initial conditions $a_0=2$, $a_1=1$. Whether we start at $a_0$ or $a_1$, the sequence is called the Lucas sequence.

Remark: Variants of this idea work for all linear homogeneous recurrences with constant coefficients. Look in particular at the recurrence $a_{n+1}=3a_n-2a_{n-1}$ that you solved successfully by thinking.

Use the same procedure. We arrive at the equation $x^2-3x+2=0$, which has roots $\alpha=2$, $\beta=1$. Now we try to find $A$ and $B$ such that $A\alpha^n+B\beta^n$ satisfies our initial conditions. So we want $A(2)+B(1)=3$, $A(2^2)+B(1^2)=5$. We get $A=1$, $B=1$. This yields the formula that you already know.

There are other general methods of doing the same thing, such as generating functions.

share|improve this answer
add comment

Besides Andre Nicolas approach you could also try the following: Generating functions, define (just for a little cleaner solution) $b_0=a_1$, $b_1=a_2$, and in general $b_m=a_{m+1}$.

Let $F(t)=\sum_{n=1}^\infty b_nt^n$. Then $$b_{n+2}=3b_{n+1}-2b_n$$$$b_{n+2}t^{n+2}=3b_{n+1}t^{n+2}-2b_nt^{n+2}$$Taking summation from $n=0$ to infinity: $$\sum_{i=2}^\infty b_it^i=3t\sum_{i=1}^\infty b_it^i-2t^2\sum_{i=0}^\infty b_it^i$$$$F(t)-b_1t-b_0=3t(F(t)-b_0)-2t^2F(t)$$Using the inital conditions:$$F(t)-5t-3=3t(F(t)-3)-2t^2F(t)$$$$F(t)(1-3t+2t^2)=3-4t$$Thus, $$F(t)=\frac{3-4t}{1-3t+2t^2}$$ Break it $$F(t)=\frac{2}{1-2t}+\frac{1}{1-t}$$and that $\sum x^k=\frac{1}{1-x}$ where the sum goes form $k=0$ to infinity we get:$$F(t)=2\sum (2t)^k+\sum t^k$$Thus $b_n=2(2^n)+1$

And moving it back to your initial sequence of $a_n$ you get indeed: $$\boxed{a_n=2^n+1}$$

share|improve this answer
add comment

Another standard method is the matrix method, which is the same as the Fibonacci sequence but with different starting vector. The same solution applies.

share|improve this answer
add comment

Here's a slightly ad hoc approach to your problem b): It's easy to see that $a_1 = 1 = 0+1 = F_0+F_2$ and that $a_2 = 3 = 1+2 = F_1+F_3$; since any linear combination of Fibonacci numbers satisfies the Fibonacci recurrence (proof: if $S_n=\sum_i a_i F_{n+i}$, then $S_{n-1}+S_n = (\sum_i a_i F_{n+i-1})+(\sum_i a_i F_{n+i}) = \sum_i a_i(F_{n+i-1}+F_{n+i}) = \sum_i a_iF_{n+i+1} = S_{n+1}$) then $a_n = F_{n-1}+F_{n+1}$ must hold for all $n$.

share|improve this answer
add comment

(I'm not sure how to write mathematical symbols here, any help appreciated) There is a really neat way of doing this easily: Say v(k) = (a(k), a(k+1)) we see that by the definition of your series, v(k+1) = A*v(k) where A = (1 1) (0 1). thus, define v(1)=(1, 3), v(k)=(A^k)*v(1). Then we diagonalize A = X^(-1)*B*X (we know how to easily diagonalize any matrices by size up to 4, if they are diagonalizable), so we see (by diagonalizing) that B= (phi 0) (0 1-phi) This way we get that: v(k) = X^(-1)*(B^k)*X*v(1) where B^k= (phi^k 0) (0 (1-phi)^k). This method works generally for any finite linear recurrence relation.

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