Thank you 
I know how to solve it I think.
Will surely help you after contest gets over.
I am not blaming you for anything. 
I flagged just because people will read other messages before answering that query as it’s from an ongoing contest.
Yup, I’ve solved it. I’ll surely explain you
can you explain, how to solve such cases :-
F(n) = a*F(n-1) + d ; if n is even
F(n) = b*F(n-1) + c ; if n is odd
@aarls It’s a simple equation
F(1) = aF(0)+d
F(2) = aF(1)+d
= a*(a*F(0)+d)+d
= a2F(0)+ad+d
F(3) = a(a2F(0)+ad+d)+d
= a3F(0)+a2+ad+d
=> F(n) = anF(0) + d (1+a+a2+…+an-1)
=> F(n) = anF(0) + d(sum of n-1 terms of gp)
It’s a formula which applies both for odd and even.
F(1) should be :-
F(1) = b*F(0) + c
but you have taken
F(1) = a*F(0) + d
?
My bad, i didn’t read it properly.
In such cases, we need to maintain two matrices and change the transformation matrix between them, in case of even and odd.
can you explain bit more please, or any good source for this??
For sake of simplicity, let us denote F(n) for even n as f(n) and for odd n as g(n).
Then the equations are
f(n)=a*g(n-1)+d …[Eq. 1]
g(n)=b*f(n-1)+c …[Eq.2]
Plugging value of f(n) from Eq.2 in Eq.1, we get
g(n)=ab*g(n-2)+bd+c
This equation can be readily solved by the following method:
Method:
Let the functional equation be h(n)=\lambda*h(n-2)+\mu
There exist two real numbers x and y such that x-y=\mu.
Then the above equation can be re-written as
h(n)-x=\lambda*h(n-2)-y
Now I will choose x and y such that
x=y/\lambda…(It will always be possible to choose them and it will be clear why I’m choosing this condition)
Then the functional equation can be re-written as
h(n)-x=\lambda*(h(n-2)-y/\lambda)
Due to the imposed condition on x and y, this reduces to
h(n)-x=\lambda*(h(n-2)-x)
Now if
Q(n)=h(n)-x, then
Q(n)=\lambda*Q(n-2)
This is basic Geometric Progression with nth term being found depending on the initial value.
Now by the above technique, we can find f(n) and g(n) explicitly without any matrices.
1 Like
I think here we can have the transformation matrix A as
[
[a, b, c, 1, 1, 0, 0],
[1, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 3, 3, 1],
[0, 0, 0, 0, 1, 2, 1],
[0, 0, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 1]
]
where my X(n) is
[ f(n), f(n-1), f(n-2), (n+1)^3 , (n+1)^2, (n+1), 1 ]
and X(x-1) is similarly
[ f(n-1), f(n-2), f(n-3), (n)^3 , (n)^2, (n), 1 ]
from this, we can easily see that
X(3) = A*X(2)
so, the recurrence relation will be
X(n) = A^(n-2) * X(2)