GATE CSE 2023 | GA Question: 3

Question

A series of natural numbers $F_1, F_2, F_3, F_4, F_5, F_6, F_7, \ldots$ obeys $F_{n+1}=F_n+F_{n-1}$ for all integers $n \geq 2$.

If $F_6=37,$ and $F_7=60,$ then what is $F_1 ?$

• A. $4$
• B. $5$
• C. $8$
• D. $9$

Comments

$F_1,F_2,F_3,…$ is not a series, it is a sequence. 

There is a fundamental difference between a series and a sequence.

I have also seen mistakes previously also in gate question paper. So, I doubt whether the gate question paper is reviewed or not. Typo is fine but I don’t know why these types of fundamental mistakes can be expected from IITs and IISc professors.  

---

Is there any other method to solve this ? Different from which in the comment .

---

There are multiple straight-forward ways to solve the given recurrence like using Generating Functions, Linear Algebra or you can write the characteristic equation for the given recurrence with constant coefficients and find the roots and get the closed-form expression with given conditions and evaluate $F_1.$ 

But it can be solved by the following two other methods and you can generalize it also if you have given like $F_{1000},F_{1001}$ and ask about $F_1.$

Method 1:

Zeckendorf’s theorem tells that “every positive integer can be represented uniquely as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers.”

Here, given recurrence is same as we use for Fibonacci numbers but different values as stated in the question.

As Fibonacci numbers $f_0,f_1,f_2,f_3,f_4,f_5,f_6,f_7,f_8,f_9,f_{10},..$ are $0,1,1,2,3,5,8,13,21,34,55,...$ (if you start the Fibonacci numbers from zero)

Here, you are given $F_7 = 60=55+5 = f_{10}+f_5$ and similarly,

 $F_6 = 37=34+3 = f_{9}+f_4$ and so, 

$F_5 =F_7 -F_6 = (f_{10} \  – \ f_9) + (f_5 -f_4) = f_8 + f_3$

Hence, in General, you can write:

$$F_i = f_{i+3} + f_{i-2}, i \geq 2$$ 

So, $F_2= f_5+f_0 = 5+0 = 5$ and $F_3= f_6+f_1 = 8+1 = 9$

Therefore, $F_1 = F_3 \ – \ F_2 = 9-5 =4$

In General, if you have given a very large positive integer, then you can find the nearest Fibonacci number by using this and write that integer with sum of one or more distinct Fibonacci numbers and then compute $F_i$ for some integer $i.$     

---

Method 2:

Let, $F_7 = \alpha$ and $F_6 = \beta$ then

$F_5 = \alpha-\beta $

$F_4 = 2\beta-\alpha $

$F_3 = 2\alpha-3\beta$

$F_2 = 5\beta-3\alpha$

$F_1 = 5\alpha-8\beta = 5\times 60 - 8\times37=300-296=4$

Here, if you observe, coefficient of $\alpha$ are $1,-1,2,-3,5$ and coefficient of $\beta$ are $-1,2,-3,5,-8$. Coefficients of $\beta$ are right shifted by one position of  coefficients of $\alpha$ with appending one consecutive Fibonacci number. And, for both, absolute values of these coefficient follows Fibonacci sequence and positive & negative signs are in alternate position. (Why ?)

Now, in general, if you have given a very large values of $\alpha$ and $\beta$ then you can find $F_1$ by observing the patterns and you can think why this pattern exists here. Since, we know the cloased-form expression for Fibonacci sequence, so you can compute $F_1$ also in case of large $\alpha$ and $\beta.$

Answer 1

it is given that $f_{n+1}=f_n+f_{n-1}$

if we put $n=6,5,4,3,2$ we get our value.

put $n=6\rightarrow f_7=f_6+f_5\implies f_5=60-37=23$

put $n=5\rightarrow f_6=f_5+f_4\implies f_4=37-23=14$

put $n=4\rightarrow f_5=f_4+f_3\implies f_3=23-14=9$

put $n=3\rightarrow f_4=f_3+f_2\implies f_2=14-9=5$

put $n=2\rightarrow f_3=f_2+f_1\implies f_1=9-5=4$

So we get $f_1=4$ option $(B)$ is correct.

Comments

This is correct but time consuming approach.

---

this is the easiest approach