SloppyTurtle's blog

Help needed with a linear recurrence
By SloppyTurtle, history, 5 years ago, In English

Hi, i`ve been trying to solve with problem 1182E - Product Oriented Recurrence. But i have some troubles with such a recurrence: F(n)=g(n)*C+F(n-1)+F(n-2)+F(n-3), where g(n)=2*n-6, n>=4 and i know F(1),F(2),F(3). How should i approach this and similar recurrences? Thanks in advance!

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

It's not a linear recurrence and I don't think there is a general way of dealing with additional terms like your $$$g(n)$$$. Rather there is a trick with this recurrence in particular.

Honestly either think more or read the editorial, currently you made a blog asking for help that's no different from reading the editorial.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Actually, there is a general method of dealing with additional terms in linear recurrences. They are called linear non-homogeneous recurrences, and solving them is similar to solving differential equations using method of undetermined coefficients. You can read about this using this PDF.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    You're wrong. cn + d term can easily be added to a matrix like so:

    0 1 0 0 0
0 0 1 0 0
1 1 1 c d
0 0 0 1 1
0 0 0 0 1
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      That's not a general way, that's a trick you can do with this recurrence.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well, depends on what you mean by general ¯\_(ツ)_/¯. Sure, you cant add a sin(x) term but doing cn+d is fairly general and standard.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ok, that's fair. I'd think a linear term is still fairly specific (although linear terms are the most common).

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            You can do that with any polynomial. The transformation from the vector (...,n^3,n^2,n^1,1) to the vector (...,(n+1)^3,(n+1)^2,(n+1),1) is linear -- i.e., each value in the right vector is a fixed linear combination of the values in the left vector.

            → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          For what it is worth, with my method, you can use $$$\sin x$$$. For example:

          $$$F_n = 2F_{n-1} + \sin(n)$$$

          Use Euler's equation to write sin(x)$ as $$$\frac{e^{ix}-e^{-ix}}{2i}$$$:

          $$$F_n = 2F_{n-1} -\frac{i}{2}e^{in} +\frac{i}{2}e^{-in}$$$

          Now, suppose that $F_n = ae^{in}+be^{-in}$ for some constants $$$a,b$$$:

          $$$ae^{in}+be^{-in}= 2(ae^{i(n-1)}+be^{-i(n-1)}) -\frac{i}{2}e^{in} +\frac{i}{2}e^{-in}$$$

          Notice that $e^{i(n-1)}=\frac{1}{e^i}e^{in}$:

          $$$ae^{in}+be^{-in}= \frac{2a}{e^i}e^{in} +2be^{i}be^{-in} -\frac{i}{2}e^{i} +\frac{i}{2}e^{-in}$$$

          Add like terms:

          $$$ae^{in}+be^{-in}= (\frac{2a}{e^i}-\frac{i}{2})e^{in} +(2be^{i}+\frac{i}{2})be^{-in}$$$

          Now, set coefficients equal to each other:

          $$$a=\frac{2a}{e^i}-\frac{i}{2}$$$
          $$$b=2be^{i}+\frac{i}{2}$$$

          Thus, $a=\frac{ie^i}{4-2e^i}$ and $$$b=\frac{i}{2-4e^i}$$$, so the following is one possible solution to $$$F_n$$$:

          $$$F_n=\frac{ie^i}{4-2e^i}e^{in}+\frac{i}{2-4e^i}e^{-in}$$$

          This provides with one particular solution. However, we then need to find the particular solution matching our initial condition. For this, we simply solve for the general solution to $F_n=2F_{n-1}$ and tack that on as a new term to our solution:

          $$$F_n=\frac{ie^i}{4-2e^i}e^{in}+\frac{i}{2-4e^i}e^{-in}+c2^n$$$

          Now, knowing $F_0$, plug $$$n=0$$$ to solve for $$$c$$$ and you have your equation.

          Here is a Python implementation of the above:

          >>> from math import cos, sin
>>> def exp(imaginary): return cos(imaginary)+1j*sin(imaginary)
>>> def func(initial, n):
...     c = initial-((1j*exp(1))/(4-2*exp(1))+1j/(2-4*exp(1)))
...     return c*2**n+1j*exp(1)/(4-2*exp(1))*exp(n)+1j/(2-4*exp(1))*exp(-n)
... 
>>> func(10, 0)
(10+0j)
>>> func(10, 1)
(20.8414709848079+0j)
>>> func(10, 2)
(42.59223939644147+0j)
>>> 2*func(10, 1)+sin(2)
(42.59223939644148+0j)

          As you can see, I tried the formula assuming $$$F_0=10$$$ and was able to verify that $$$2F_1+\sin(2)=F_2$$$, which shows that the equation works.

          → Reply
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Well, $$$Cg(n)=2Cn-6C$$$ is clearly a linear function, so let's assume that $$$F(n)$$$ is also a linear function $$$mn+b$$$. Then, we get:

$$$mn+b=2Cn-6C+m(n-1)+b+m(n-2)+b+m(n-3)+b$$$
$$$mn+b=(2C+3m)n-6C-6m+3b$$$
$$$0=(2C+2m)n-6C-6m+2b$$$

Thus, $2C+2m=0$, so $$$m=-C$$$, and $$$-6C-6m+2b=-6C+6C+2b=2b=0$$$, so $$$b=0$$$. Thus, we know that $$$F(n)=-Cn$$$ is at least one solution to the linear recurrence. However, this might not meet the initial conditions required by $$$F(1),F(2),F(3)$$$.

Thus, we need to solve the characteristic equation of the linear recurrence. After doing this, we find the following solution:

$$$x^3-x^2-x-1=0 \implies x \approx 1.8393 \text{ or } x \approx -0.41964 \pm 0.60629i$$$

Thus, our final solution is:

$$$F(n)=-Cn+c_1 1.8393^n+c_2(-0.41964+0.60629i)^n+c_3(-0.41964-0.60629i)^n$$$

Now, plug in $n=1,2,3$ and use Gaussian elimination to solve for $$$c_1,c_2,c_3$$$. Remember that these coefficients could be complex numbers. Good luck!

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Let the current state vector be $$$\left(f_n, f_{n-1}, f_{n-2}, n, 1 \right)$$$. You can construct a Matrix $$$M_{5 \times 5}$$$, such that

$$$\left(f_n, f_{n-1}, f_{n-2}, n, 1 \right) \times M = \left(f_{n+1}, f_{n}, f_{n-1}, n+1, 1 \right)$$$

To calculate $$$f_n$$$,

$$$\left(f_3, f_{2}, f_{1}, 3, 1 \right) \times M^{n-3} = \left(f_{n}, f_{n-1}, f_{n-2}, n, 1 \right)$$$

You can use binary exponentiation to calculate $$$M^k$$$ in $$$O(\log{k})$$$.

→ Reply