0 votes 0 votes Solve the recurrence relation $a^{2}n-5a^{2}_{n-1}+4a^{2} _{n-2}=0$, if $a_{0}=4, a_{1}=13, n>1$ Combinatory discrete-mathematics combinatory recurrence-relation + – kidussss asked Jul 8, 2022 • recategorized Jul 8, 2022 by Arjun kidussss 482 views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply ankitgupta.1729 commented Jul 9, 2022 reply Follow Share Let, $a_n^2 =T_n$ So, given recurrence becomes $T_n – 5T_{n-1} + 4T_{n-2} = 0$ with $T_0 = a_0^2 = 16$ and $T_1 = a_1^2 = 13^2$ Now, can you proceed from here ? 1 votes 1 votes kidussss commented Jul 9, 2022 i edited by kidussss Jul 9, 2022 reply Follow Share Please help me... and show all the necessary steps 0 votes 0 votes ankitgupta.1729 commented Jul 9, 2022 reply Follow Share $T_n\; - 5T_{n-1} + 4T_{n-2} = 0$ with $T_0 = 16$ and $T_1 = 13^2$ It is a linear homogeneous recurrence of order $2.$ Suppose, I am guessing its solution as $T_n = c\alpha^n ;c\neq 0 $ which means this solution will satisfy the recurrence and so, $c\alpha^n – 5c\alpha^{n-1} + 4c\alpha^{n-2} = 0$ $\alpha^n – 5\alpha^{n-1} + 4\alpha^{n-2} = 0 , c\neq 0$ $\alpha^n – 5\alpha^{n-1} + 4\alpha^{n-2} = 0 $ $\alpha^2 – 5\alpha + 4 = 0 $ $\alpha^2 – 4\alpha – \alpha + 4 = 0 $ $\alpha=1,4$ So, $T_n = c_1 (1)^n + c_2 (4)^n$ $T_n = c_1 + c_2 4^n$ For $n=0,$ $T_0 = c_1 +c_2 \implies c_1 + c_2 = 16$ For $n=1,$ $T_1 = c_1 +4c_2 \implies c_1 + 4c_2 = 169$ From these 2 equations in $c_1$ and $c_2,$ we get, $c_2=51, c_1 = -35$ Hence, $T_n =51*4^n -35$ Since, $a_n^2 = T_n$ It means $a_n = \pm \sqrt{51*4^n -35}$ You could verify it for $n=2,3,...$ 1 votes 1 votes Nagend123 commented Jul 13, 2022 reply Follow Share @ankitgupta.1729. @kidussssIt is $a^2n$ and not $a^2_n$ ? 0 votes 0 votes ankitgupta.1729 commented Jul 14, 2022 reply Follow Share @Nagend123 it must be a typo otherwise question does not make sense. If you consider $a^2n$ then what should be the “a” ? One thing I missed in the above solution that I have guessed the solution for $T_n$ but have not proved it. Suppose, $T_n = 51 \times 4^n \ – \ 35$ is true for all $n,n-1,….,0$ (Inductive Hypothesis) Now, we need to prove that $T_{n+1} = 51 \times 4^{n+1} – 35$ (Inductive Step) As we have a recurrence $T_n -5T_{n-1} + 4T_{n-2} = 0$ If we put $n:=n+1$ then recurrence becomes $T_{n+1} -5T_{n} + 4T_{n-1} = 0$ which implies $T_{n+1} = 5T_{n} - 4T_{n-1} $ According to our inductive hypothesis, put the values of $T_n$ and $T_{n-1},$ we get $T_{n+1} = 5(51 \times 4^n – 35) - 4(51 \times 4^{n-1} – 35) $ $T_{n+1} = 5 \times 51 \times 4^n – 5 \times 35 - 4\times 51 \times 4^{n-1} + 4 \times 35 $ $T_{n+1} = 5 \times 51 \times 4^n\ –\ 5 \times 35 - 51 \times 4^{n}\ + \ 4 \times 35 $ $T_{n+1} = 51 \times 4^{n+1}\ –35 $ Hence, $T_n = 51 \times 4^n \ – \ 35$ is true for all integer $n \geq 0$ 0 votes 0 votes mahendrapatel commented Jul 15, 2022 reply Follow Share na,i think its a square index n 0 votes 0 votes Please log in or register to add a comment.