1.3k views
Solve the following recurrence relation

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

$x_1=2$

edited | 1.3k views
+5
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$
+2

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

2n - 2n-1 + 1

=> 212n-1 - 2n-1 + 1

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

=> 2n-1 + 1

0
where have you got answer as logn?

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

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

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

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

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

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

$\dots$

$=2^{n-1}T(n-(n-1)) - \left(2^{n-2} +2^{n-3}+\dots+2^2 + 2 +1\right)$
$=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}$

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

$=2^{n-1} + 1$
by Veteran (115k points)
edited by
+5
There is a nice method explained in keneth and rosen maths book for this type of problem.
0
where?
+2
@shrestha same with the solution given by @manoj
0
is it possible to fetch the answer by putting the various value ...

in reccurance problem many question i did by just puting the value

need help ?
0
What is the significance of "-1"? How come it can take -1(constant) time?
0

@srestha how to find  number of terms in gp?

how did you conclude that n=n-1?

0
n=n-1??
+1

@Iarnav

terms in GP are from 20 to 2n-2 So total term =n-1.

0

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

Another alternative is:

by Boss (38.3k points)
0
please tell me sir , when i apply this method and explain the procedure to solve these type of question using this method
0
This is nothing but simple method of solving recurrence relation treating homogenous solution and particular solution separately and then building final recurrence relation.
0
can uh please tell me procedure bro
0

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

0
just give the one line hint
O(2^n)
by (193 points)

1
2