edited by
5,739 views
21 votes
21 votes
Solve the following recurrence relation

$x_n = 2x_{n-1}-1, n>1$

$x_1=2$
edited by

3 Answers

Best answer
43 votes
43 votes
$T(n) = 2T(n-1) -1$

$\qquad =2(2T(n-2)-1) -1$

$\qquad =2^2T(n-2) -2 -1$

$\qquad =2^2(2T(n-3)-1) -2 -1$

$\qquad =2^3T(n-3) - 2^2 -2 -1$

$\qquad \dots $

$\qquad =2^{n-1}T(n-(n-1)) - \left(2^{n-2} +2^{n-3}+\dots+2^2 + 2 +1\right)  $
$\qquad =2^{n-1}\times 2 - \frac{2^{n-1}-1}{2-1}  \because T(1) = 2, S_n = \frac{a.\left(r^n -1\right)}{r-1}$

$\qquad =2^n - \left(2^{n-1} -1\right)$

$\qquad =2^{n-1} + 1$
edited by
23 votes
23 votes

Another alternative is:

0 votes
0 votes
$x_{n}\ =\ 2x_{n-1}\ –\ 1 $

$2x_{n}\ =\ 2^{2}x_{n-1}\ –\ 2^{1} $

……

……

$2^{k}x_{n-k}\ =\ 2^{k+1}x_{n-k-1}\ –\ 2^{k} $

…….

…….

$2^{n-2}x_{2}\ =\ 2^{n-1}x_{1}\ –\ 2^{n-2} $

 

After adding all the equations, all the $x_{i}$ related terms will cancel out and only $x_{n}$ willbe left in the LHS and $x_{1}=2$ in the RHS.

$x_{n}\ =\ 2^{n-1}.2\ -\ (1 + 2^{2}+2^{3}+…… 2^{n-2})  $

$x_{n}\ =\ 2^{n}\ -\ 2^{n-1}\ +\ 1  = 2^{n-1}\ +\ 1  $

Related questions

29 votes
29 votes
6 answers
1
Kathleen asked Sep 25, 2014
13,710 views
What value would the following function return for the input $x=95$?Function fun (x:integer):integer; Begin If x 100 then fun = x – 10 Else fun = fun(fun (x+11)) End;$...
26 votes
26 votes
3 answers
2
Kathleen asked Sep 25, 2014
7,741 views
Give the correct matching for the following pairs: $$\begin{array}{ll|ll}\hline \text{(A)} & \text{$O (\log n)$} & \text{(P)} & \text{Selection} \\\hline \text{(B)} & \t...
25 votes
25 votes
2 answers
3
Kathleen asked Sep 25, 2014
9,053 views
Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?Dynamic programmingBacktrackingGreedyDivide and Conqu...
13 votes
13 votes
4 answers
4
Arjun asked Aug 12, 2018
4,122 views
Let $R$ be a binary relation on $A = \{a, b, c, d, e, f, g, h\}$ represented by the following two component digraph. Find the smallest integers $m$ and $n$ such that $m <...