0

Solve the recurrence relation $u_n = 2u_{n-1} + 2^n - 1$ where n is greater than or equal to 1 and $u_0=0$.

We have characteristic root equal to 2 with multiplicity 1. So homogeneous part will have solution $A.2^n$, where A is constant. The particular solution should be of the form $P.n.2^n + Q$, where P, Q are constants. Now when I put this in original recurrence I can't solve. Plz help.

Vibhav
  • 115

1 Answers1

2

HINT: Multiply out the righthand side:

$$\begin{align*} Pn2^n+Q&=2P(n-1)2^{n-1}+2Q+2^n-1\\ &=P(n-1)2^n+2Q+2^n-1\\ &=Pn2^n-(P-1)2^n+2Q-1 \end{align*}$$

Subtract $Pn2^n+Q$ from both sides and rearrange a little:

$$Q-1=(P-1)2^n$$

This has to hold for all $n\ge 0$, so what must $P$ be? And what does that force $Q$ to be?

Brian M. Scott
  • 616,228
  • There can be many values for P and Q. How can I get the values if the equation has three unknowns P, Q and n? – Vibhav Dec 06 '15 at 02:42
  • $n$ is not an unknown – as Brian writes, this is meant to be an identity that holds for all values of $n$. – Gerry Myerson Dec 06 '15 at 06:25
  • @user5267640: If you don't see why the fact that it holds for all $n$ forces $P$ to have a certain value, you can use a slightly more brute force approach. It holds for $n=0$, so $Q-1=P-1$. It also holds for $n=1$; that gives you another equation in $P$ and $Q$; solve that pair of equations for $P$ and $Q$. – Brian M. Scott Dec 06 '15 at 08:09
  • It means I can take two values of n arbitrarily and find two equations in P and Q. When I did this for n= 0, 1 I got P = Q =1. Am I right? – Vibhav Dec 06 '15 at 08:20
  • Do you have to ask? – Gerry Myerson Dec 06 '15 at 12:06
  • @user5267640: Yes, that’s correct. Note that this can be seen without actually going to all that trouble. The value of $2^n$ changes as $n$ changes, so if $P-1\ne 0$, $(P-1)2^n$ is not a constant. Clearly $Q-1$ is a constant, so the only way the two can be equal for all $n$ is for $P-1$ to be $0$, i.e., for $P$ to be $1$. In that case $(P-1)2^n$ is always $0$, so $Q-1$ has to be $0$ as well, and therefore $Q=1$. – Brian M. Scott Dec 06 '15 at 14:15
  • Yeah. I got that. Thanks everyone for the valuable advice. – Vibhav Dec 07 '15 at 02:58