Given
X = [ 1 1 1 ] , X ′ = [ 1 1 1 ] , A = [ − 1 2 3 0 1 6 0 0 − 1 ] X=\begin{bmatrix}1\\1\\1\end{bmatrix},
\qquad
X' = \begin{bmatrix}1&1&1\end{bmatrix},
\qquad
A=\begin{bmatrix}-1&2&3\\0&1&6\\0&0&-1\end{bmatrix} X = 1 1 1 , X ′ = [ 1 1 1 ] , A = − 1 0 0 2 1 0 3 6 − 1 We need to find k ∈ N k\in \mathbb{N} k ∈ N
X ′ A k X = 33. X' A^k X=33. X ′ A k X = 33.
Interpret the expression
Let
Y k = A k X . Y_k=A^k X. Y k = A k X . Then
X ′ A k X = X ′ Y k X' A^k X = X'Y_k X ′ A k X = X ′ Y k is just the sum of the entries of Y k Y_k Y k X ′ = [ 1 1 1 ] X'=[1\ 1\ 1] X ′ = [ 1 1 1 ]
So we first compute A k X A^kX A k X
Use the triangular structure of A A A
Let
Y k = [ a k b k c k ] = A k X . Y_k=\begin{bmatrix}a_k\\b_k\\c_k\end{bmatrix}=A^kX. Y k = a k b k c k = A k X . Since
Y k + 1 = A Y k , Y_{k+1}=AY_k, Y k + 1 = A Y k , we get the recurrence from
A [ a k b k c k ] = [ − a k + 2 b k + 3 c k b k + 6 c k − c k ] . A\begin{bmatrix}a_k\\b_k\\c_k\end{bmatrix}
=
\begin{bmatrix}-a_k+2b_k+3c_k\\b_k+6c_k\\-c_k\end{bmatrix}. A a k b k c k = − a k + 2 b k + 3 c k b k + 6 c k − c k . Thus,
a k + 1 = − a k + 2 b k + 3 c k , a_{k+1}=-a_k+2b_k+3c_k, a k + 1 = − a k + 2 b k + 3 c k , b k + 1 = b k + 6 c k , b_{k+1}=b_k+6c_k, b k + 1 = b k + 6 c k , c k + 1 = − c k , c_{k+1}=-c_k, c k + 1 = − c k , with initial values from Y 0 = X Y_0=X Y 0 = X
a 0 = b 0 = c 0 = 1. a_0=b_0=c_0=1. a 0 = b 0 = c 0 = 1.
Solve for c k c_k c k b k b_k b k
From
c k + 1 = − c k , c 0 = 1 , c_{k+1}=-c_k, \quad c_0=1, c k + 1 = − c k , c 0 = 1 , we get
c k = ( − 1 ) k . c_k=(-1)^k. c k = ( − 1 ) k . Now
b k + 1 = b k + 6 ( − 1 ) k , q u a d b 0 = 1. b_{k+1}=b_k+6(-1)^k,
quad b_0=1. b k + 1 = b k + 6 ( − 1 ) k , q u a d b 0 = 1. Compute first few terms:
b 1 = 1 + 6 = 7 b_1=1+6=7 b 1 = 1 + 6 = 7 b 2 = 7 − 6 = 1 b_2=7-6=1 b 2 = 7 − 6 = 1 b 3 = 1 + 6 = 7 b_3=1+6=7 b 3 = 1 + 6 = 7
So the pattern is
b k = { 1 , k even 7 , k odd b_k=
\begin{cases}
1, & k \text{ even}\\
7, & k \text{ odd}
\end{cases} b k = { 1 , 7 , k even k odd which can be written as
b k = 4 − 3 ( − 1 ) k . b_k=4-3(-1)^k. b k = 4 − 3 ( − 1 ) k .
Solve for a k a_k a k
We have
a k + 1 = − a k + 2 b k + 3 c k . a_{k+1}=-a_k+2b_k+3c_k. a k + 1 = − a k + 2 b k + 3 c k . Substitute b k = 4 − 3 ( − 1 ) k b_k=4-3(-1)^k b k = 4 − 3 ( − 1 ) k c k = ( − 1 ) k c_k=(-1)^k c k = ( − 1 ) k
a k + 1 = − a k + 2 ( 4 − 3 ( − 1 ) k ) + 3 ( − 1 ) k a_{k+1}=-a_k+2\bigl(4-3(-1)^k\bigr)+3(-1)^k a k + 1 = − a k + 2 ( 4 − 3 ( − 1 ) k ) + 3 ( − 1 ) k = − a k + 8 − 6 ( − 1 ) k + 3 ( − 1 ) k = -a_k+8-6(-1)^k+3(-1)^k = − a k + 8 − 6 ( − 1 ) k + 3 ( − 1 ) k = − a k + 8 − 3 ( − 1 ) k . = -a_k+8-3(-1)^k. = − a k + 8 − 3 ( − 1 ) k . Now compute a few values starting from a 0 = 1 a_0=1 a 0 = 1
a 1 = − 1 + 8 − 3 = 4 a_1=-1+8-3=4 a 1 = − 1 + 8 − 3 = 4 a 2 = − 4 + 8 + 3 = 7 a_2=-4+8+3=7 a 2 = − 4 + 8 + 3 = 7 a 3 = − 7 + 8 − 3 = − 2 a_3=-7+8-3=-2 a 3 = − 7 + 8 − 3 = − 2 a 4 = 2 + 8 + 3 = 13 a_4=2+8+3=13 a 4 = 2 + 8 + 3 = 13
This suggests separate even/odd formulas. Let
s k = X ′ A k X = a k + b k + c k . s_k=X'A^kX=a_k+b_k+c_k. s k = X ′ A k X = a k + b k + c k . Instead of fully solving a k a_k a k s k s_k s k
Using the above:
k = 0 k=0 k = 0 ( a 0 , b 0 , c 0 ) = ( 1 , 1 , 1 ) (a_0,b_0,c_0)=(1,1,1) ( a 0 , b 0 , c 0 ) = ( 1 , 1 , 1 ) s 0 = 3 s_0=3 s 0 = 3 k = 1 k=1 k = 1 ( 4 , 7 , − 1 ) (4,7,-1) ( 4 , 7 , − 1 ) s 1 = 10 s_1=10 s 1 = 10 k = 2 k=2 k = 2 ( 7 , 1 , 1 ) (7,1,1) ( 7 , 1 , 1 ) s 2 = 9 s_2=9 s 2 = 9 k = 3 k=3 k = 3 ( − 2 , 7 , − 1 ) (-2,7,-1) ( − 2 , 7 , − 1 ) s 3 = 4 s_3=4 s 3 = 4 k = 4 k=4 k = 4 ( 13 , 1 , 1 ) (13,1,1) ( 13 , 1 , 1 ) s 4 = 15 s_4=15 s 4 = 15
We see:
for even k k k s k = 3 , 9 , 15 , … s_k=3,9,15,\dots s k = 3 , 9 , 15 , …
for odd k k k s k = 10 , 4 , − 2 , … s_k=10,4,-2,\dots s k = 10 , 4 , − 2 , …
Let us derive the exact formulas.
Separate even and odd indices
From the recurrence:
For even k = 2 m k=2m k = 2 m
We observe
b 2 m = 1 , c 2 m = 1. b_{2m}=1,\qquad c_{2m}=1. b 2 m = 1 , c 2 m = 1. So
a 2 m + 1 = − a 2 m + 2 ( 1 ) + 3 ( 1 ) = − a 2 m + 5. a_{2m+1}=-a_{2m}+2(1)+3(1)=-a_{2m}+5. a 2 m + 1 = − a 2 m + 2 ( 1 ) + 3 ( 1 ) = − a 2 m + 5. Also for odd index,
b 2 m + 1 = 7 , c 2 m + 1 = − 1 , b_{2m+1}=7,\qquad c_{2m+1}=-1, b 2 m + 1 = 7 , c 2 m + 1 = − 1 , so
a 2 m + 2 = − a 2 m + 1 + 2 ( 7 ) + 3 ( − 1 ) = − a 2 m + 1 + 11. a_{2m+2}=-a_{2m+1}+2(7)+3(-1)=-a_{2m+1}+11. a 2 m + 2 = − a 2 m + 1 + 2 ( 7 ) + 3 ( − 1 ) = − a 2 m + 1 + 11. Substitute a 2 m + 1 = − a 2 m + 5 a_{2m+1}=-a_{2m}+5 a 2 m + 1 = − a 2 m + 5
a 2 m + 2 = − ( − a 2 m + 5 ) + 11 = a 2 m + 6. a_{2m+2}= -(-a_{2m}+5)+11 = a_{2m}+6. a 2 m + 2 = − ( − a 2 m + 5 ) + 11 = a 2 m + 6. Since a 0 = 1 a_0=1 a 0 = 1
a 2 m = 1 + 6 m . a_{2m}=1+6m. a 2 m = 1 + 6 m . Hence for even k = 2 m k=2m k = 2 m
s 2 m = a 2 m + b 2 m + c 2 m = ( 1 + 6 m ) + 1 + 1 = 6 m + 3. s_{2m}=a_{2m}+b_{2m}+c_{2m}=(1+6m)+1+1=6m+3. s 2 m = a 2 m + b 2 m + c 2 m = ( 1 + 6 m ) + 1 + 1 = 6 m + 3. For odd k = 2 m + 1 k=2m+1 k = 2 m + 1
Using
a 2 m + 1 = − a 2 m + 5 = − ( 1 + 6 m ) + 5 = 4 − 6 m . a_{2m+1}=-a_{2m}+5=-(1+6m)+5=4-6m. a 2 m + 1 = − a 2 m + 5 = − ( 1 + 6 m ) + 5 = 4 − 6 m . Thus
s 2 m + 1 = a 2 m + 1 + b 2 m + 1 + c 2 m + 1 = ( 4 − 6 m ) + 7 − 1 = 10 − 6 m . s_{2m+1}=a_{2m+1}+b_{2m+1}+c_{2m+1}=(4-6m)+7-1=10-6m. s 2 m + 1 = a 2 m + 1 + b 2 m + 1 + c 2 m + 1 = ( 4 − 6 m ) + 7 − 1 = 10 − 6 m .
Set the expression equal to 33
We need
s k = 33. s_k=33. s k = 33. If k = 2 m k=2m k = 2 m
6 m + 3 = 33 6m+3=33 6 m + 3 = 33 6 m = 30 6m=30 6 m = 30 m = 5. m=5. m = 5. So
k = 2 m = 10. k=2m=10. k = 2 m = 10. If k = 2 m + 1 k=2m+1 k = 2 m + 1
10 − 6 m = 33 10-6m=33 10 − 6 m = 33 which is impossible for natural m m m
Therefore,
k = 10 . \boxed{k=10}. k = 10 .
Compare with stored answer
Stored correct answer: 10 10 10
Our derived answer is also 10 10 10