504 views
0 votes
0 votes

Solve the following recurrence relation :-

N(h)=N(h−1)+N(h−2)+1 

1 Answer

0 votes
0 votes

Theorem

Let c1 and c2 be real numbers. Suppose that r2 − c1r − c2 = 0 has two distinct roots r1
and r2. Then the sequence {an} is a solution of the recurrence relation an = c1an−1 + c2an−2
if and only if an = α1r1n+ α2r2n
 for n = 0, 1, 2, . . . , where α1 and α2 are constants.

 

Related questions

1 votes
1 votes
0 answers
1
srestha asked May 19, 2019
596 views
Let $A(n)$ denotes the number of $n$ bit binary strings which have no pair of consecutive $1’s.$ what will be recurrence relation for it and what will be it’s Time Co...
1 votes
1 votes
2 answers
2
srestha asked May 10, 2019
847 views
What is the solution of recurrence relation$T\left ( n \right )=T\left ( n-1 \right )+n$
1 votes
1 votes
1 answer
3
VikramRB asked Jan 20, 2019
1,005 views
What is the time complexity of the following recurrence relation and step to derive the same$T(n) = T(\sqrt{n}) + log(logn)$
1 votes
1 votes
1 answer
4
Mayankprakash asked Jan 4, 2019
1,271 views
T(n) = T(n/4) + T(3n/4) + nHow to solve these type of problems?Can I solve this using master theorm by considering X = T(3N/4) +N THEN T(N) = T(N/4) +XCAN WE SOLVE LIKE T...