Finding $C_n=4C_{n-1}+6n-1$

Question

2.$$\begin{cases} C_n=4C_{n-1}+6n-1\\ C_0=2\\ \end{cases} $$

$\begin{cases} C_n=D_n+dn+e\\ D_n=\lambda D_{n-1}\end{cases}$

$D_n+dn+e=4C_{n-1}+6n-1$

But $C_{n-1}=D_{n-1}+d(n-1)+e$

So $D_n+dn+e=4(D_{n-1}+d(n-1)+e)+6n-1$

$D_n+dn+e=4D_{n-1}+4dn-4d+4e+6n-1$

But for $\lambda=4$ we get $4D_{n-1}+dn+e=4D_{n-1}+4dn-4d+4e+6n-1$ and

$0=-dn-e+4dn-4d+4e+6n-1$ or $0=(3d+6)n+3e-4d-1$

So $d=-2,e=1.5$

$C_n=D_n+dn+e$ So $C_n=D_n-2n+1.5$ And $C_0=D_0+1.5$ So $2=D_0+1.5$ And $D_0=-0.5$

$D_n=4D_{n-1}$

So

$C_n=D_n+dn+e=4^n-2n+1.5$ which is $O(4^n)$

Is it correct?

Answer 1

No, it's not correct.

$3d+6=0$ and $3e-4d-1=0$ gives $d=-2$ and $e=-\frac73$.

From $D_n=4D_{n-1}$, we get $D_n=D_0 4^n$ with $D_0 = C_0 - 0d - e = 2 + \frac73 = \frac{13}{3}$, that is, $D_n=\frac{13}{3} 4^n$.

This gives $C_n = D_n -2n -\frac73 = \frac{13}{3} 4^n -2n -\frac73 = \frac13 (13 \cdot 4^n - 6 n - 7)$.

Your other mistake was concluding that $D_n=4^n$ instead of $D_n=D_0 4^n$.

Answer 2

We start by solving the homogenous part: letting $x^n=C_n$ gives the characteristic equation $$x^n=4x^{n-1}\Rightarrow x=4,$$ which gives $$C_n=A(4^n).$$ Now, for the the inhomogenous part, let us guess that the solution is of the form $$p(n)=d_0+d_1n,$$ substituting into the recurrence gives $$d_0+d_1n=4(d_0+d_1(n-1))+6n-1,$$ which, by comparing coefficients gives $$d_0=-\frac{7}{3},\quad d_1=-2.$$ The final solution is obtained by adding the homogenous and inhomogenous parts; and thus $$C_n=A(4^n)-\frac{7}{3}-2n.$$ Finally, we may find $A$ by imposing the initial condition $$2=A-\frac{7}{3}\Rightarrow A=\frac{13}{3}.$$ This therefore gives $$C_n=\frac{13}{3}(4^n)-\frac{7}{3}-2n.$$

Answer 3

$$C_1=4C_0+6\cdot1-1,$$ $$\frac{1}{4}C_2=C_1+\frac{1}{4}(6\cdot2-1),$$ $$\frac{1}{4^2}C_3=\frac{1}{4}C_2+\frac{1}{4^2}(6\cdot3-1),$$ $$.$$ $$.$$ $$.$$ $$\frac{1}{4^{n-1}}C_n=\frac{1}{4^{n-2}}C_2+\frac{1}{4^{n-1}}(6n-1),$$ which after summing gives $$\frac{1}{4^{n-1}}C_n=4\cdot2+6\left(1+\frac{2}{4}+\frac{3}{4^2}+...+\frac{n}{4^{n-1}}\right)-\left(1+\frac{1}{4}+\frac{1}{4^2}+...+\frac{1}{4^{n-1}}\right)=$$ $$=8+6\left(1+2x+3x^2+...+4x^{n-1}\right)_{x=\frac{1}{4}}-\frac{\left(\frac{1}{4}\right)^n-1}{\frac{1}{4}-1}=$$ $$=\frac{20}{3}+\frac{4}{3}\left(\frac{1}{4}\right)^n+6(x+x^2+...+x^n)'_{x=\frac{1}{4}}=$$ $$=\frac{20}{3}+\frac{4}{3}\left(\frac{1}{4}\right)^n+6\left(\frac{x(x^n-1)}{x-1}\right)'_{x=\frac{1}{4}}=$$ $$=\frac{20}{3}+\frac{4}{3}\left(\frac{1}{4}\right)^n+\frac{6\left(nx^{n+1}-(n+1)x^n+1\right)}{(x-1)^2}_{x=\frac{1}{4}}=$$

$$=\frac{20}{3}+\frac{4}{3}\left(\frac{1}{4}\right)^n+\frac{6\left(n\left(\frac{1}{4}\right)^{n+1}-(n+1)\left(\frac{1}{4}\right)^n+1\right)}{\left(\frac{1}{4}-1\right)^2}=$$ $$=\frac{52}{3}+\left(\frac{1}{4}\right)^n\left(-8n-\frac{28}{3}\right).$$ Thus, $$C_n=\frac{52}{3}\cdot4^{n-1}-2n-\frac{7}{3}.$$