Expressin reccurence equation with formula

Question

I am trying to solve reccurent equation:

$X_{n} = 2X_{n-1} + 1 , n > 1 , X_{1} = 2$

My solutions is as following

$X_{n} = 1 + 2X_{n-1}$

$ = 1 + 2 ( 1 + 2X_{n-2})$

$ = 1 + 2 ( 1 + 2( 1 + 2X_{n-3}))$

$ = 1 + 2 ( 1 + 2( 1 + 2...( 1 + 2*2))$

So $X_1 = 2$ , $X_2 = 5$, $X_3 =11$ , $X_4 = 23$.

But i fail to see the pattern , how can we express this equation with formula?

We add $1$ $n$ times so we have to add $+ n$ in the formula. Also every layer is multiplied by $2$ . The only formula that came to my mind is

$n + 1 + 2\sum_{i=0}^{n-1}i$

Which match only about every second index right. What is the right way to express this problem with formula?

Answer 1

Write $y_n=x_n+1$ and solve $y_n=2y_{n-1}$.

Answer 2

Hint: Keep multiplying. $X_n$ in terms of $X_{n-k}$ is like $$X_n = 1+2X_{n-1}$$ $$X_n = 1+2(1+2X_{n-2})=1+2+4X_{n-2}$$ $$X_n = 1+2+4+8X_{n-3}=\sum _{i=0}^22^i+2^3X_{n-3}$$ $$\vdots$$ $$X_n = \sum _{i=0}^{k-1}2^i+2^kX_{n-k}$$ What happens when $k=n-1?$, then use geometric sum.

Answer 3

Hint: Let $X_n=y_n+an+b$

$1=X_n-2X_{n-1}=y_n+an+b-2(y_{n-1}+a(n-1)+b$

$1=y_n-2y_{n-1}-an-b+2a$

Choose $a=0, b=-1$