4
$\begingroup$

I am self-studying Discrete Mathematics. Here is one question I am suppose to solve.

a) $x_{n+1}=2x_{n}+1,x_{1}=2$

When I tried to find the homogeneous solution to $x_{n+1}=2x_{n}$ I found $a_{n}=2^{n}$, but it shoud be $a_{n}=2^{n-1}.$ I don't know why I should put $a_{1}=1$. What I am doing wrong?

1 Answers 1

4

We find a solution of the homogeneous equation. Your $2^n$ sounds good.
Of course $2^{n-1}$ also works, for that matter $2^{n+47}$ is OK too. But I like $2^n$ best, it is easiest to type. (Please do not look at the initial condition yet, wait until we have the general solution of the recurrence.)

We find a solution to the inhomogeneous equation. Try for a constant solution $k$; we find that $-1$ works.

So the general solution of the recurrence is $-1+C2^n$, where $C$ is any constant. Now let $x_1=2$. We get $2C-1=2$, so $C=3/2$. The solution is therefore $-1+(3/2)2^n$.

We can rewrite this as $3\cdot 2^{n-1}-1$. If we had used $2^{n-1}$ as one solution of the homogeneous equation, we would get general solution $-1+D2^{n-1}$, and find that $D=3$. No difference.