0 votes 0 votes T(n) = 3T(n-1) -4T(n-2) + 2T(n-3) If n = 0 then T(n) = 1 if n= 1 or 2 then T(n) = 0 What is the generalized solution? Algorithms algorithms recurrence-relation + – kumar123 asked Sep 25, 2022 • retagged Sep 26, 2022 by Shubham Sharma 2 kumar123 590 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Pranavpurkar commented Sep 26, 2022 reply Follow Share I am not getting any series bro , how can I generalize it? source of this question? 0 votes 0 votes Abhrajyoti00 commented Sep 26, 2022 reply Follow Share T(0) = 1, T(1) = 0, T(2) = 0, T(n) = 3T(n-1) -4T(n-2) + 2T(n-3) - Wolfram|Alpha (wolframalpha.com) It shows no solution. 1 votes 1 votes nameaman2170 commented Sep 26, 2022 reply Follow Share If we do this by recursion tree method, Left subtree will go till $3^{n}$, middle subtree will go till $4^{n/2} = 2^{n}$ and right subtree will go till $2^{n/3}$. Overall time = $O(3^{n})$. 1 votes 1 votes Pranavpurkar commented Sep 26, 2022 reply Follow Share nameaman2170 it is asking for the generalized solution . no doubt it is np complete. 1 votes 1 votes ankitgupta.1729 commented Sep 26, 2022 reply Follow Share $T_n = 3T_{n-1} \ – \ 4T_{n-2} + 2T_{n-3}$ with $T_0=1,T_1=T_2=0$ or, $T_n - 3T_{n-1} \ + \ 4T_{n-2} - 2T_{n-3} = 0$ with $T_0=1,T_1=T_2=0$ This is a linear homogeneous recurrence of order 3. So, suppose, given recurrence has a solution $T_n = c\alpha^n; c \neq 0$ [Since, we are guessing the solution, later we can prove that our guessed solution is correct by using induction.] Now, our guessed solution will satisfy the recurrence. So, $c\alpha^n \ – \ 3c\alpha^{n-1} + 4c \alpha^{n-2} \ – \ 2c\alpha^{n-3} = 0$ $\alpha^3 – 3\alpha^2 + 4\alpha \ – \ 2 = 0$ (This is our characteristic polynomial and we need to find its roots.) $\alpha^3 \ – \ \alpha^2 \ – \ 2\alpha^2 + 4\alpha \ – \ 2 = 0$ $\alpha^2(\alpha \ -\ 1) \ – \ 2(\alpha\ – \ 1)^2 = 0$ $(\alpha-1) (\alpha^2 \ – \ 2\alpha + 2) = 0$ Hence, $\alpha = 1, 1\pm i$ Therefore, Solution of the given recurrence is: $T_n = a_1\times 1^n + a_2 (1+i)^n +a_3 (1-i)^n $ So, $T_n = a_1 + a_2 (1+i)^n +a_3 (1-i)^n $ where $a_1,a_2,a_3$ are arbitrary constants. Now, to find $a_1,a_2,a_3,$ you need to use $T_0=1,T_1=T_2=0$ and most important thing is here $a_1,a_2,a_3$ are not reals. These are complex numbers, so you need to assume like $a_1=x_1 + iy_1,a_2=x_2 + iy_2,a_3=x_3 + iy_3.$ You can try to find the reason why these are not reals by assuming it reals and what will be the values of $a_1,a_2,a_3.$ Try it. If you stuck, I will attach the further solution to find $a_1,a_2$ and $a_3.$ At the end you will get the same solution which @Abhrajyoti00 has mentioned above. 1 votes 1 votes Please log in or register to add a comment.