Let `A_n` be `n`th term of your sequence. Your sequence is recursively defined as ` `

`A_(n+1)=A_n+A_(n-1),\ n=2,3,ldots,\ \ \ A_1=3,\ A_2=4` **(1)**

Formula for sum of first n terms of your sequence is

`sum_(k=1)^n A_k=A_(n+2)-4` ...

## Unlock

This Answer NowStart your **48-hour free trial** to unlock this answer and thousands more. Enjoy eNotes ad-free and cancel anytime.

Already a member? Log in here.

Let `A_n` be `n`th term of your sequence. Your sequence is recursively defined as ` `

`A_(n+1)=A_n+A_(n-1),\ n=2,3,ldots,\ \ \ A_1=3,\ A_2=4` **(1)**

Formula for sum of first n terms of your sequence is

`sum_(k=1)^n A_k=A_(n+2)-4` **(2)**

We will prove this formula by use of mathematical induction

**i)** `A_1+A_2=3+4=7=11-4=A_4-4`

**ii)** Assume that formula (2) holds for all natural numbers less or equal to `n`.

**iii)**

`sum_(k=1)^(n+1)A_k=sum_(k=1)^(n)A_k+A_(n+1)` now we use assumption ii)

`=A_(n+2)-4+A_(n+1)` now we use recursive relation (1)

`A_(n+3)-4=A_(n+2+1)-4`

which proves formula (2).

Of course formula (2) doesn't give you the way to calculate `A_(n+2)` without calculating all the previous terms of the sequence. For that you need to find non-recursive formula for term `A_n` which is not an easy task. If you are interested the formula for `n`th term is

`A_n=(-2)^-n (f)^(-1 -n) cdot`

`((-1)^n (f)^(2 n) (2+f) +2^n (4 (-f)^(1 + n) + 2^n (f-4) +2 (--2-f)^n (1+f)))`

where `f=1+sqrt(5)`.

If you want to know more about recursions and combinatorics in general click here.