0

$f_n = 13f_{n-2} + 12f_{n - 3} + 2n + 1$

Ok so first I was to find the solution for the $13f_{n-2} + 12f_{n - 3}$ portion. There are 3 roots, however, so I am not sure which ones to use in my general solution. Also, I'm stuck trying to find the particular solution for the $ 2n + 1$ portion. If anyone could guide me in solving this recurrence, I would very grateful! Thanks!

Barry Cipra
  • 79,832
nikki
  • 143
  • and where are the initial conditions? – Dr. Sonnhard Graubner Nov 18 '14 at 20:44
  • Use the solution you got for $f_n = 13_{f_{n-2}} + 12_{f_{n - 3}}$ and add a term like $A+Bn$ and identify. – Claude Leibovici Nov 18 '14 at 20:51
  • @Dr.SonnhardGraubner. I think that we can solve the problem without any initial condition. Can't we ? – Claude Leibovici Nov 18 '14 at 20:53
  • Why are the $f_i$'s subscripts of the coefficients? I'm unfamiliar with what that represents. – Andrey Kaipov Nov 18 '14 at 20:53
  • I added the initial conditions just now. The thing is $13_{f_{n - 2}} + 12_{f_{n-3}}$ has 3 roots (-3, 1 and 4) and there are only 2 terms, so which root values do I use? – nikki Nov 18 '14 at 20:53
  • You use all three since the relation is of order $3$. – Andrey Kaipov Nov 18 '14 at 20:56
  • 1
    @nikki. Do you know that, when speaking about a recurrence relation, you tell "a thing" you could be taken to court ! Joke for sure. Cheers. – Claude Leibovici Nov 18 '14 at 20:57
  • As Andrey notes, this looks strange. Are you sure you don’t mean for the recurrence to be $f_n = 13f_{n-2} + 12f_{n - 3} + 2n + 1$? The way you’ve written it, $f_3=13_{f_1}+12_{f_0}+7=13_1+12_0+7$. What does that mean? – Steve Kass Nov 18 '14 at 21:03
  • @Andrey so what would the solution for that part be? $-3^n a_1 +4^n a_2 - 1$? – nikki Nov 18 '14 at 21:04
  • or maybe it is $-3^n a_1 + 4^n a_2 - a_3$? – nikki Nov 18 '14 at 21:06
  • @SteveKass the subscripts means that these two previous terms are used in finding the current term we're looking for. For example, for $f_3$ we use the terms $f_1$ and $f_0$ to find the solution. I'm trying to find the overall general solution for the recurrence though. – nikki Nov 18 '14 at 21:10
  • Nikki, your subscripts have subscripts. Going by your equation, the way you "use" $f_1$ is very odd. You put $f_1$ as a subscript to the number 13. What is $13_1$? I'm pretty sure you mean for the recurrence to be $f_n = 13f_{n-2} + 12f_{n - 3} + 2n + 1$, but this is not what you wrote. You have written 13-subscript-something, not 13-times-something. – Steve Kass Nov 18 '14 at 21:19
  • @SteveKass Oh! I'm sorry, I typed it up wrong! Yes I do mean exactly what you just typed! Hopefully that clears things up, hopefully you can help me solve it :) – nikki Nov 18 '14 at 21:22

2 Answers2

1

I rewrite the relation (for personal preference) as: $$f_{n+3} - 13{f_{n+1}} - 12{f_{n}} = 2(n+3) + 1=2n+7,$$ which is valid for $n\ge0$. Then the characteristic polynomial is $r^3 - 13r-12=0$ whose roots are $r=-3,-1,4$. We use all of the roots since the relation is of order $3$. So the complementary solution to the corresponding homogenous recurrence relation is $$f^c_n = a_1(-3)^n +a_2 (-1)^n+ a_34^n.$$

Now assume the particular solution is of the form $f_n = sn+t$. Then $f_{n+1} = sn+s+t$, and $f_{n+3} = sn + 3s+t$. We can substitute these back into the original relation, match coefficients with respective powers of $n$, and solve for both $s$ and $t$: $$sn+3s+t-13(sn+s+t) -12(sn+t) = 2n+7.$$ We find that $s=-\frac{1}{12}$ and $t=-\frac{37}{144}$.

Now adding the particular and complementary solutions is the general solution to our original recurrence relation.

Andrey Kaipov
  • 2,857
  • 1
  • 18
  • 23
  • Thanks! I am not understanding the 2n + 7 portion though. Why did you re-write it to that? – nikki Nov 18 '14 at 21:34
  • I rewrote the recurrence relation so it's valid for $n\ge 0$. That way they're more reminiscent of differential equations, in my opinion. – Andrey Kaipov Nov 18 '14 at 21:35
0

If you try a linear expression, $f_n=a+bn$, $$a+bn=13(a+b(n-2))+12(a+b(n-3))+2n+1=25a-62b+1+(25b+2)n.$$ By identification, $$a=25a-62b+1,\\b=25b+2.$$