GATE CSE 1998 | Question: 6a

Question

Solve the following recurrence relation

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

$x_1=2$

Comments

Trace the pattern:
$x1 = 2$
$x2 = 2*x1 -1 = 2*2 -1 = 3 = 2^1 + 1$
$x3 = 2*x2 -1 = 2*3 -1 = 5 = 2^2 + 1$
$x4 = 2*x3 -1 = 2*5 -1 = 9 = 2^3 + 1$
$x5 = 2*x4 -1 = 2*9 - 1 = 17  = 2^4 + 1$

Hence, answer is $2^{n-1} +1$

---

For those who are wondering, 2ⁿ - 2^n-1 + 1 = 2^n-1 + 1 ? 

2ⁿ - 2^n-1 + 1 

=> 2¹2^n-1 - 2^n-1 + 1

=> 2^n-1(2 - 1) + 1

=> 2^n-1 + 1

---

where have you got answer as logn?

i'm getting 2^(n-1)+1

@Pratik Raghuvanshi​​​​​​ please check it.

---

@vishalshrm539 or we can understand it like this as well  $2^{n}$ –  $2^{n-1}$+1 

we can write it in simple terms $2^{n}$ – $2^{n}/2$ +1 $\Rightarrow$     $2^{n} \left (1- 1/2 \right ) +1$ 

Answer 1

$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$

Comments

@ Bad_Doctor  Thank you brother!

---

Given recurrence

$x_n=2x_{n-1}-1$......(1)

Associated Linear recurrence relation

$x_n=2x_{n-1}$ and solution to the homogenous part is

$x_n^{H}=\alpha2^n$ for some constant $\alpha$

Particular solution will be of the form $x_n^{P}=d$ for some constant $d$.

Subsitute form of the particular solution in (1) to get d

$d=2d-1 \rightarrow d=1$

Full solution is given by $x_n=x_n^{H}+x_n^{P}=\alpha2^n+1$

Using initial condition we get $\alpha=1/2$

$x_n=2^{n-1}+1$

---

@Ayush Upadhyaya Here a =2 right in the third last equation where did the three suddenly disappear for equation a (r^n-1)/r-1

Answer 2

Another alternative is:

Comments

can uh please tell me procedure bro

---

i know but to find the homogenous solution but did not know particular solution

please someone tell me how to put d (or any other variable which we take), in the particular solution 

means how to form the equation for prticular solution 

@Ayush Upadhyaya @Magma

---

just give the one line hint

Answer 3

$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  $