reopened by
683 views
0 votes
0 votes

The solution of the recurrence relation

$a_{r} = a_{r-1} + 2a_{r-2}$ with $a_{0} = 2,a_{1} = 7$ is

  1. $a_{r} = (3)^{r} + (1)^{r}$
  2. $2a_{r} = (2)^{r}/3 – (1)^{r}$
  3. $a_{r} = 3^{r+1} – (-1)^{r}$
  4. $a_{r} = 3(2)^{r} – (-1)^{r}$
reopened by

1 Answer

0 votes
0 votes

Refer this link for solving recurrence relations(a very good read):  Solving recurrences

The question is in the form of second-order recurrence relation  :     $C_{0}x_{r}+C_{1}x_{r-1}+C_{2}x_{r-2}=0$

The characteristic equation of the recurrence is given by:    $C_{0}m^{2}+C_{1}m+C_{2}=0$ (refer the link above for detailed explanation).

$\therefore$  The given recurrence can be written as :   $a_{r}-a_{r-1}-2a_{r-2}=0$

$\Rightarrow$   $m^{2}-m-2=0$   $\Rightarrow$    $(m+1)(m-2)=0$    $\Rightarrow$   $m_{1}=-1$   and  $m_{2}=2$

For real and distinct roots of the quadratic equation, the solution to the recurrence is given by :   $x_{r}=c_{1}m_{1}^{r}+c_{2}m_{2}^{r}$

Using the given data of   $T_{0}$ and $T_{1}$, we get    $c_{1}(-1)^{0}+c_{2}(2)^{0}=2$   and   $c_{1}(-1)^{1}+c_{2}(2)^{1}=7$

$\Rightarrow$    $c_{1}=-1$  and    $c_{2}=3$

$\therefore$   Solution to the recurrence would be:   $a_{r}=3(2)^{r}-(-1)^{r}$

Option D is correct.

 

 

Answer:

Related questions

0 votes
0 votes
0 answers
1
1 votes
1 votes
2 answers
2
2 votes
2 votes
1 answer
3
admin asked Apr 1, 2020
1,039 views
The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number number of nodes in a binary tree of height $h$ is $2^{h}$$2^{h-1} ...
0 votes
0 votes
1 answer
4
admin asked Apr 1, 2020
1,558 views
Web links are stored within the page itself and when you wish to ‘jump’ to the page that is linked, we select the hotspot or anchor. This technique is calledHypertext...