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 need some help with the following non-homogenous recurrence relation.

$$a_n-2a_{n-1}+a_{n-2}=n+1$$ $$a_0=0, a_1=1$$

When I solve the associated homogenous equation I use the auxiliary equation $x^2-2x+1=0$ and obtain the root $x=1$. Hence, I obtain the equation $a_n=(A+nB)1^n$. Using the initial conditions I get $a_n=n$.

When it comes to the particular solution I get stuck, however. I thought the solution should be on the form $cn+d$ due to $n+1$. The following calculations show how I then get stuck:

$$a_n-2a_{n-1}+a_{n-2}=n+1$$ $$cn+d-2(c(n-1)+d)+c(n-2)+d=n+1$$ $$cn+d-2(cn-c+d)+cn-2c+d=n+1$$ $$cn+d-2cn+2c-2d+cn-2c+d=n+1$$ $$0=n+1$$

So obviously I am wrong about the form of the particular solution.

share|improve this question
    
You can't use inhomogeneous initial condition for homogeneous problem. –  Kaster Nov 28 '13 at 17:34
    
Can you expand on that? –  tychicus Nov 28 '13 at 17:47
    
You said that to find $a_n$ you use initial conditions, but you can't do that since initial conditions are from different inhomogeneous problem. –  Kaster Nov 28 '13 at 18:31

1 Answer 1

up vote 0 down vote accepted

Use difference solution. Define $\Delta a_k=a_k-a_{k-1}$: $$ \Delta a_k- \Delta a_{k-1}=k+1\\ \Delta a_{k-1} - \Delta a_{k-2}=k\\ \ldots\\ \Delta a_2-\Delta a_1 = k-(k-3) $$ Now sum LSH and RHS. On LHS you'll get $\Delta a_k - \Delta a_1$, on RHS $k(k-1)+1 - S_{k-3}$, where $S_{k-3} = 1+2+\ldots +k-3$. Clearly $\Delta a_1=1$ so you get $$ \Delta a_{k}= 2 +k(k-1)-S_{k-3} $$ Now sum over $k$ over both sides. On LHS you'll get $a_n$ and on RHS some expression $O(n^3)$ after some algebra. Note $\frac{2k(k-1)}{2}-\frac{(k-3)(k-2)}{2}=\frac{k^2-3k-6}{2}.$

share|improve this answer
    
Thank you for the help. –  tychicus Dec 5 '13 at 16:35
    
You are welcome –  Alex Dec 5 '13 at 16:40

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.