0

I've been trying to solve this generating function:

$f(n)-5f(n-1)-6f(n-2)=2^n+n$

This is how I approached it. I divided it into:

$f(n)-5f(n-1)-6f(n-2)=2^{n+1}$ and $f(n)-5f(n-1)-6f(n-2)=2n$

I then calculated the homogeneous and particular solution by making the substitution: $f(n)=A\alpha^n$ for computing the homogeneous solution and for the particular solution $f(n)=2^n(p_0)$ for the first and similarly for the second and I substituted these in the original equations(the ones I divided it into). (This procedure was taught if the $RHS$ was the product of a polynomial and exponent) The complete solution is the sum of the homogeneous and particular solution.

Am I right in assuming that the sum of the solutions for the equations which are split up will yield the solution for $f(n)-5f(n-1)-6f(n-2)=2^n+n$

3.14159
  • 183
  • 1
    You can get the particular solution in one go. First, the homogeneous solution looks like $$f_h(n)=A\cdot 6^n+B\cdot(-1)^n$$ for each $n\in\mathbb{Z}$ (here, $A$ and $B$ are fixed constants). A good Ansatz for the particular solution is to assume that $$f_p(n)=an+b+c\cdot 2^n$$ for some constants $a,b,c$. – Batominovski Aug 22 '18 at 15:24
  • Thanks. I got it – 3.14159 Aug 22 '18 at 15:27
  • As an additional comment: it is true that any $f$ which satisfies those two equations will also satisfy the original; but it is not true that any $f$ that satisfies the original need satisfy the latter two. In fact, the latter two equations are inconsistent: finding such an $f$ would imply that $2^{n+1}=2n$ for all $n$, which is of course not true. – Nick Peterson Aug 22 '18 at 15:37
  • @NickPeterson So you’re basically saying my approach is wrong, right? – 3.14159 Aug 22 '18 at 15:48
  • There's nothing inherently wrong with the approach of trying to take a complicated recurrence and split it into more manageable pieces. I'm more saying that this particular split, in this particular case, won't work. – Nick Peterson Aug 22 '18 at 15:51
  • Alright, thanks. I understand – 3.14159 Aug 22 '18 at 16:00

2 Answers2

2

Since you have been explained why your approach does not work, I am providing a synthetic solution (without making any Ansatz about how a particular solution should look like). It is not an elegant solution, but it can serve to explain why I suggested that you make a particular Ansatz in a comment above.

Define the right shift operator $S$ on the set of functions from $\mathbb{Z}$ to $\mathbb{C}$ by $$(Sg)(n):=g(n-1)\text{ for all }n\in\mathbb{Z}\,,\text{ where }g:\mathbb{Z}\to\mathbb{C}\text{ is arbitrary.}$$ Let $I$ denote the identity operator, namely, $Ig:=g$. We see that $$\big((I-5S-6S^2)f\big)(n)=2^n+n\,.$$ Hence, $$\big((I+S)(I-6S)\big)f(n)=2^n+n\,.$$ Let $F:=(I-6S)f$. Then, $$\big((I+S)F\big)(n)=2^n+n\,.$$ Consequently, $$\begin{align}F(n)-(-1)^n\,F(0)&=\big((I-(-1)^nS^n)F\big)(n) \\&=\Big((I-S+S^2-\ldots+(-1)^{n-1}S^{n-1})(I+S)F\Big)(n) \\&=(I-S+S^2-\ldots+(-1)^{n-1}S^{n-1})\big(2^n+n\big) \\&=\small\left(2^n-2^{n-1}+2^{n-2}-\ldots+(-1)^{n-1}2\right)+\big(n-(n-1)+(n-2)-\ldots+(-1)^{n-1}\big) \\&=\left(\frac{(-1)^{n-1}2+2^{n+1}}{3}\right)+\left\lceil\frac{n}{2}\right\rceil \\&=\left(\frac{(-1)^{n-1}2+2^{n+1}}{3}\right)+\frac{n+\left(\frac{1-(-1)^n}{2}\right)}{2} \\&=\frac{1}{2}\,n+\frac{1}{4}+\frac{2}{3}\,2^n-\frac{11}{12}\,(-1)^n\,. \end{align}$$ In other words, $$\big((I-6S)f)(n)=F(n)=\frac{1}{2}\,n+\frac{1}{4}+\frac{2}{3}\,2^n+\left(F(0)-\frac{11}{12}\right)\,(-1)^n\,.$$ Then, we again have $$\begin{align} f(n)-6^n\,f(0)&=\big((I-6^nS^n)f\big)(n)\\ &=\Big((I+6S+6^2S^2+\ldots+6^{n-1}S^{n-1})(I-6S)f\Big)(n)\\ &=\small (I+6S+6^2S^2+\ldots+6^{n-1}S^{n-1})\Biggl(\frac{1}{2}\,n+\frac{1}{4}+\frac{2}{3}\,2^n+\left(F(0)-\frac{11}{12}\right)\,(-1)^n\Biggr) \\ &=\frac{1}{2}\,\Big(n+6(n-1)+6^2(n-2)+\ldots+6^{n-1}\Big)+\frac14\,\big(1+6+6^2+\ldots+6^{n-1}\big) \\ &\phantom{aaaaa}+\frac23\,\Big(2^n+6\cdot 2^{n-1}+6^2\cdot 2^{n-2}+\ldots+6^{n-1}\cdot 2\Big) \\ &\phantom{aaaaaaaaaa}+\left(F(0)-\frac{11}{12}\right)\,\Big((-1)^n+6\cdot(-1)^{n-1}+6^2\cdot(-1)^{n-2}+\ldots+6^{n-1}\cdot(-1)\Big) \\ &=\small\frac12\,\Biggl(-\frac{n}{5}+\frac{6}{5}\,\left(\frac{6^n-1}{5}\right)\Biggr)+\frac{1}{20}\,\left(6^n-1\right)+\frac{2}{3}\,\Biggl(2^n\,\left(\frac{3^n-1}{2}\right)\Biggr) +\left(F(0)-\frac{11}{12}\right)\,\left(\frac{(-1)^n-6^n}{7}\right) \\ &=-\frac{1}{10}\,n-\frac{17}{100}-\frac{1}{3}\,2^n+\left(\frac{111}{175}-\frac{1}{7}\,F(0)\right)\,6^n+\left(\frac{1}{7}\,F(0)-\frac{11}{84}\right)\,(-1)^n\,. \end{align}$$ Consequently, $$f(n)=-\frac{1}{10}\,n-\frac{17}{100}-\frac{1}{3}\,2^n+\left(\frac{111}{175}-\frac{1}{7}\,F(0)+f(0)\right)\,6^n+\left(\frac{1}{7}\,F(0)-\frac{11}{84}\right)\,(-1)^n\,.$$ Since $F(0)=f(0)-6\,f(-1)$ and $f(-1)=\dfrac{f(1)-5\,f(0)-3}{6}$, we get $$F(0)=3+6f(0)-f(1)\,.$$ That is, $$f(n)=\small-\frac{1}{10}\,n-\frac{17}{100}-\frac{1}{3}\,2^n+\left(\frac{36}{175}+\frac17\,f(0)+\frac17\,f(1)\right)\,6^n+\left(\frac{25}{84}+\frac67\,f(0)-\frac17\,f(1)\right)\,(-1)^n$$ for all $n\in\mathbb{Z}$.

Batominovski
  • 49,629
  • I'm afraid I'm not equipped with the skills to completely make sense of what's going on here. What does a shift operator mean? – 3.14159 Aug 24 '18 at 12:22
  • 1
    We have $(Sg)(n)=g(n-1)$. For example, if $g(n)=n^2$ for all $n\in\mathbb{Z}$, then $$(Sg)(3)=g(3-1)=g(2)=2^2=4,.$$ Likewise, $$\begin{align}(S^3g)(10)&=(S^2g)(10-1)=(S^2g)(9)\&=(Sg)(9-1)=(Sg)(8)\&=g(8-1)=g(7)=7^2=49,.\end{align}$$ – Batominovski Aug 24 '18 at 14:45
1

If you have found a function $f$ which satisfies $$f(n)-5f(n-1)-6f(n-2)=2^n$$ and a function $ g$ which satisfies $$g(n)-5g(n-1)-6g(n-2)=n$$

then the function $(f+g)$ will satisfies

$$(f+g)(n)-5(f+g)(n-1)-6(f+g)(n-2)= f(n)-5f(n-1)-6f(n-2)+ g(n)-5g(n-1)-6g(n-2)=2^n+n $$

Mohammad Riazi-Kermani
  • 68,728