Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.