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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer

Your Answer


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.