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!
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.
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.
You're wrong. cn + d term can easily be added to a matrix like so:
That's not a general way, that's a trick you can do with this recurrence.
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.
Ok, that's fair. I'd think a linear term is still fairly specific (although linear terms are the most common).
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.
For what it is worth, with my method, you can use $$$\sin x$$$. For example:
Use Euler's equation to write sin(x)$ as $$$\frac{e^{ix}-e^{-ix}}{2i}$$$:
Now, suppose that $F_n = ae^{in}+be^{-in}$ for some constants $$$a,b$$$:
Notice that $e^{i(n-1)}=\frac{1}{e^i}e^{in}$:
Add like terms:
Now, set coefficients equal to each other:
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$$$:
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:
Now, knowing $F_0$, plug $$$n=0$$$ to solve for $$$c$$$ and you have your equation.
Here is a Python implementation of the above:
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.
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:
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:
Thus, our final solution is:
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!
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
To calculate $$$f_n$$$,
You can use binary exponentiation to calculate $$$M^k$$$ in $$$O(\log{k})$$$.