### SloppyTurtle's blog

By SloppyTurtle, history, 3 months ago, ,

Hi, ive 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!

• +5

 » 3 months ago, # |   +3 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.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +3 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.
•  » » 3 months ago, # ^ |   +5 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 
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 That's not a general way, that's a trick you can do with this recurrence.
•  » » » » 3 months ago, # ^ |   0 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.
•  » » » » » 3 months ago, # ^ |   0 Ok, that's fair. I'd think a linear term is still fairly specific (although linear terms are the most common).
•  » » » » » » 3 months ago, # ^ |   +3 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.
•  » » » » » 3 months ago, # ^ |   +3 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.  » 3 months ago, # | +7 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!
 » 3 months ago, # | ← Rev. 2 →   0 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})$.