fibonacci series - a slight variant

Let me define a recurence like this

S(1) = 1
S(2) = 1

S(n) = S(n-1) + S(n-2) + a; where a is some number

Q1: What is the relation beween S(n) and F(n) [nth Fibonacci number]

I found out this is S(n) = F(n) + K(n)*a

Where K(n) is another series of the type S(n) where a = 1

Q2: Is there a way to find the generic term for S(n) ?

Any pointers will be of great help. Thanks

Well, you can always use the theory of difference equations (recurrence relations). You can find the nth term of the Fibonacci sequence this way, and I'm sure your S(n) sequence can be found the same way. The theory is very similar to that of differential equations.

Let $\displaystyle f(n) $ be a sequence that $\displaystyle f(n+2) = f(n+1) + f(n) $ , not necessarily be Fibonacci seq. , depends on the initial conditions .



Then we have $\displaystyle S(n) = f(n) - a $ because

$\displaystyle f(n+2) - a = f(n+1) + f(n) - a = (f(n+1) - a) + (f(n) - a ) + a $

$\displaystyle = S(n+1) + S(n) + a $

Quote:

---

Originally Posted by aman_cc

Let me define a recurence like this

S(1) = 1
S(2) = 1

S(n) = S(n-1) + S(n-2) + a; where a is some number

Q1: What is the relation beween S(n) and F(n) [nth Fibonacci number]

I found out this is S(n) = F(n) + K(n)*a

Where K(n) is another series of the type S(n) where a = 1

Q2: Is there a way to find the generic term for S(n) ?

Any pointers will be of great help. Thanks

---

We have $\displaystyle S_3=2+a, \; S_4=3+2a $.

You can use induction to show $\displaystyle S_n=F_n+a\cdot (F_n-1) $.

Edit: Credit goes to Soroban's post below. I had made a mistake.

Hello, aman_cc!

Quote:

---

Let me define a recurence like this:

. . $\displaystyle S(1) = 1$
. . $\displaystyle S(2) = 1$
. . $\displaystyle S(n) \:= \:S(n\!-\!1) + S(n\!-\!2) + a\:\text{ for some constant }a.$

What is the relation beween $\displaystyle S(n)$ and $\displaystyle F(n)$, the $\displaystyle n^{th}$ Fibonacci number?

---

Crank out the first few terms:

.$\displaystyle \begin{array}{|c||c|c|}n & S(n) & F(n)\\ \hline
1 & 1 & 1\\
2 & 1 & 1\\
3 & 2+a & 2 \\
4 & 3+2a & 3\\
5 & 5+4a & 5 \\
6 & 8 + 7a & 8 \\
7 & 13 + 12a & 13 \\
8 & 21 + 20a & 21 \\
\vdots & \vdots & \vdots
\end{array}$


And we see that: . $\displaystyle S(n) \;=\;F(n) + [F(n)-1]\cdot a $

Thanks for all the posts