The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+16 votes
1.2k views
Solve the following recurrence relation

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

$x_1=2$
asked in Algorithms by Veteran (408k points)
edited by | 1.2k 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

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

3 Answers

+26 votes
Best answer
$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$
answered by Veteran (112k 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

@ Bad_Doctor  Thank you brother!

0
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$
+17 votes

Another alternative is:

answered by Boss (38.2k 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 

@Ayush Upadhyaya @Magma

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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,587 questions
54,197 answers
187,535 comments
71,151 users