recurrence relation

Question

Which recurrence relation satisfy the sequence: 2, 3, 4, . . ., for n ≥ 1.

A ) T(N) = 2 T(N-1) - T(N-2)

   

B)T(N) = T(N-1) + T(N-2)

C)T(N) = N+1

D)

None of these

Comments

Option A is the correct answer!

if you are thinking about C, then it is not recurrence relation, it is solution of it!

---

yes . option a is true

 

but how we take  t(0) and t(-1)

if in option A we take

T(1) = 2 T(0) - T(-1)

---

 Ashwin Kulkarni PLZ CHECK THIS ONE

---

Actually T(1) = 2 and T(2) = 3 will be the base conditions for this relation.

Hence no need to check for T(-1) or T(0) because they have given n>=1.

---

@Ashwin Kulkarni why not  T(N) = N+1  is true.

can you explain plz...??

---

@rajoramanoj

T(n) = n+1 is a solution of this recurrence relation.

---

this option is also correct .....or not

---

answer must be option D

A can't be true bcz in question n>=1 but in A we can't able to find a1

C is wrong bcz it is not a recurrence equation.

---

 rajoramanoj  we have to find recurrence relation ( which calls itself) not solution of this recurrence relation.

that 's why c i wrong.

---

@akb1115

A) is correct.

take base condition as T(0)=1 and T(-1)=0

T(1) = 2T(0) - T(-1) = 2

T(2) = 2T(1) - T(0) = 3.......and so on.

---

There should be a base condition like T(1)= …. Or T(0)=….. ,

Answer 1

Since it is given that n>=1, we cannot assume T(0) or T(-1) just take base conditions as T(1)=2 and T(2)=3 then option A is correct.