0

I want to proof that for every recurrence relation in the form: $$f(n) = C_1\cdot f(n-1) + C_2\cdot f(n-2) + ... + C_r\cdot f(n-r) + P(n)\cdot x^n$$ where $x$ is constant root for the related homogeneous relation and $P(n)$ is a polynomial from degree $t$ there is another polynomial from degree at most $t$, $Q(n)$, for which the form: $h(n) = (Q(n))\cdot (n^m)\cdot (x^n)$ where $m$ is the multiplicity of the root $x$ in the related homogeneous relation, $h(n)$ is a particular solution for the recurrence relation.

I understand that for doing that in need the proof the for the equation: $$h(n) = C_1\cdot h(n-1) + ... C_r + P(n)\cdot x^n,$$ there is always a solution, but I am having difficulties doing that, can someone maybe help me to start with it? any guide or help would be very appreciated.

Thank you

LegNaiB
  • 2,757
  • 4
  • 26
tom sabala
  • 1
  • How does the related homogeneous relation where $x$ is a root from, look like? – LegNaiB Jun 07 '21 at 07:44
  • if f(n)=C1⋅f(n−1)+C2⋅f(n−2)+...+Cr⋅f(n−r)+P(n)⋅xn is my recurrence relation, than f(n)=C1⋅f(n−1)+C2⋅f(n−2)+...+Cr⋅f(n−r) is the associated homogeneous relation and i consider x to be the root if it. and it looks like P(t) = t^n -C1^n-1 - ... - Cr = (t-x)^m ⋅ q(t) – tom sabala Jun 07 '21 at 09:02

0 Answers0