Given the matrix:
\[
A =
\begin{pmatrix}
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0
\end{pmatrix}
\]

Calculate: A^n

Solution:
\[
A^2 =
\begin{pmatrix}
2 & 1 & 1 \\
1 & 2 & 1 \\
1 & 1 & 2
\end{pmatrix}
\]

\[
A^3 =
\begin{pmatrix}
2 & 3 & 3 \\
3 & 2 & 3 \\
3 & 3 & 2
\end{pmatrix}
\]

\[
A^4 =
\begin{pmatrix}
6 & 5 & 5 \\
5 & 6 & 5 \\
5 & 5 & 6
\end{pmatrix}
\]

\[
A^5 =
\begin{pmatrix}
10 & 11 & 11 \\
11 & 10 & 11 \\
11 & 11 & 10
\end{pmatrix}
\]

\[
A^n =
\begin{pmatrix}
a_n & b_n & b_n \\
b_n & a_n & b_n \\
b_n & b_n & a_n
\end{pmatrix}
\]

\[
A^{n 1} =
\begin{pmatrix}
a_{n 1} & b_{n 1} & b_{n 1} \\
b_{n 1} & a_{n 1} & b_{n 1} \\
b_{n 1} & b_{n 1} & a_{n 1}
\end{pmatrix}
\]
\[
=
\begin{pmatrix}
2b_n & a_n b_n & a_n b_n \\
a_n b_n & 2b_n & a_n b_n \\
a_n b_n & a_n b_n & 2b_n
\end{pmatrix}
\]


\[
\implies \left\{
\begin{array}{l l}
a_{n 1} = 2b_n \\
b_{n 1} = a_n b_n \\
\end{array} \right.
\]
\Leftrightarrow
\[
\left\{
\begin{array}{l l}
a_n = 2b_{n-1} \\
b_{n 1} = 2b_{n-1} b_n\\
\end{array} \right.
\]

... and here I get stuck. How should I calculate b_n from b_n = b_{n 1} - 2 b_{n-1} ?

There should have been A^{n+1} and (a_n) + (b_n) instead of (a_n)(b_n). I don't know what went wrong. :|

\left \[ \Rightarrow \left\{ \begin{matrix}
a_n = 2b_{n-1} \\
b_{n+1} = 2b_{n-1} + b_n
\end{matrix} \right \} \right \]

\Leftrightarrow
\left \[ \left\{ \begin{matrix}
a_n = 2b_{n-1} \\
b_{n+1} = 2b_{n-1} + b_n
\end{matrix} \right \} \right \]


...and here I get stuck. How should I calculate b_n from b_n = b_{n+1} - 2 b_{n-1} ?


Consider instead that

b_n=2b_{n-2}+b_{n-1}

That gives you a recursive relationship to find b_n.

Getting from there to a closed-form equation for b_n is pretty complicated. I'll give you an abridged version of how I did it:

First, let's start expanding the nth term into subsequent lower-order terms. Since I'm too lazy to write b's and subscripts over and over again, I'm going to use a boldface italic number m to indicate b_{n-m}. For example, 32 means 3b_{n-2}; 125 means 12b_{n-5}; etc.

0 (i.e. b_n)
22+1
64+53
226+215
868+857
...

There are several things to see here: First, notice that the coefficient on the left is always equal to twice the sum of the two coefficients from the previous line. Second, notice the coefficient on the right is always equal to the sum of the left-hand coefficient from the previous line, plus three times the right-hand coefficient. More importantly, however, notice that the coefficient on the right is also always simply one less than the one on the left. Finally, notice that if we continue this process as far as we can go (about n/2 iterations), we're eventually going to end up with terms containing either b_1 and b_2 or b_0 and b_1, depending whether n is odd or even, respectively. Either way, we know a priori that b_0=0, b_1=1, and b_2=1. So as long as we can find the coefficients, we can calculate the value of b_n.

As I said before, each coefficient on the left is equal to twice the sum of the coefficients from the previous line. Therefore it seems like our formula is going to be some convoluted recursive combination of coefficient pairs. However, things are greatly simplified by the fact that the coefficient on the right is always one less than the one on the left. So if we call our right-hand coefficient a, our left-hand coefficient is always a+1. Adopting this notation instead, let's repeat our expansion from above:

(a+1)2 + a1
(4a+2)4 + (4a+1)3
(16a+6)6 + (16a+5)5
(64a+22)8 + (64a+21)7
...

Now we can see the pattern. The left-hand coefficient is made up of an a term, whose coefficient is simply increasing powers of 4, and a constant term whose value is a sum of powers of 4 (1+4+16+64+... ). The right-hand coefficient is, as always, simply one less than that on the left.

So from that pattern, the fact that a=1 (since b_n=2b_{n-2}+b_{n-1}=(a+1)b_{n-2}+(a)b_{n-1}), and our prior knowledge of the values of b_0, b_1, and b_2, we can write down the answer:

If n is odd:

b_n=2^{n-2}+1+2\sum_{m=0}^{\frac{n-5}{2}}{4^m}

And if n is even:

b_n=2^{n-2}+\sum_{m=0}^{\frac{n-4}{2}}{4^m}

Furthermore, we can write the sum in closed-form as well using the following identity:

\sum_{i=0}^{k}{j^i}=\frac{j^{k+1}-1}{j-1}

Thus if n is odd:

b_n=2^{n-2}+\frac{2}{3}\(4^{\frac{n-3}{2}}-1\)+1

And if n is even:

b_n=2^{n-2}+\frac{1}{3}\(4^{\frac{n-2}{2}}-1\)

Thank you. I've been struggling to solve it for a few days, but now I'm so happy that I finally see the method. However, I didn't quite catch where you got the expressions from when n is odd / even.

I didn't quite catch where you got the expressions from when n is odd / even.

Assuming you followed my convoluted logic up to the point of

(a+1)2 + a1
(4a+2)4 + (4a+1)3
(16a+6)6 + (16a+5)5
(64a+22)8 + (64a+21)7
...

I just sort of empirically wrote down the formula, but I think I can explain it:

First, in the case that n is odd, this procedure will ultimately boil down to coefficients of b_1 and b_2, both of which equal 1. Likewise, a=1 as well.

So in the odd case, the answer for b_n will be the sum of the left- and right-hand coefficients (without the a's). For example, if n=9, my expansion above goes to completion (there's nothing else after the... ).

The coefficient in front of the a is 4^0 on the first line, then 4^1 on the second line, 4^2 on the third, and 4^3 on the last line. Notice also that each subsequent line corresponds to an expansion by two more orders of n. In other words, the left-hand coefficient on the first line corresponds to b_{n-2} (a.k.a. 2), then 4 on the next line, then 6, then finally 8. That's as far as we need to go because b_{n-8}=b_1 which is where we stop.

Since we decrease the order by two on each subsequent line, the total number of lines goes like n/2. To be exact, it's actually (n-1)/2, since we start at n and end at 1.

As for the power-of-4 term in front of the a's, the power goes up with the number of lines. But the exponent starts at 0, not 1, so the final coefficient ends up being 4^{\frac{n-1}{2}-1}=4^{\frac{n-3}{2}}=2^{n-3}. Since, for the odd case, there are two of these terms which add together (one from the left-hand side and one from the right), we finally end up with 2(2^{n-3})=2^{n-2}.

Meanwhile, for the "constant" term on the right-hand side of each line, you can see that it's simply a sum of powers of 4, starting on the second line. The term is 4^0 on line 2, then 4^0+4^1 on line 3, then 4^0+4^1+4^2 on line 4. Now, since the coefficients don't start adding up until line 2, there are only (n-3)/2 of them. Plus, given the fact that the first term is to the 0 power, not 1, that means that the highest power on the last line is (n-3)/2 - 1 = (n-5)/2. Thus the constant term on the right-hand side is \sum_{m=0}^{\frac{n-5}{2}}4^m. The constant from the left-hand side is exactly the same, plus 1. Hence for the odd-n case, the total of the constant terms is 2\(\sum_{m=0}^{\frac{n-5}{2}}4^m\)+1.

For the n-is-even case the logic is pretty similar. The big difference there is that the left-hand term vanishes when we're done because we're down to b_0=0 for that side. Hence only the right-hand side matters.

Given that, the coefficient of the a term is slightly different. Now we're going from order n to 0 by 2 each time, so there are a total of n/2 lines (instead of (n-1)/2 like in the odd case). It still starts with 4^0, so the power of 4 on the last line will be one less than the number of lines: 4^{\frac{n}{2}-1}=4^{\frac{n-2}{2}}=2^{n-2}. Meanwhile, the summation term follows the same logic as before except that again there are now n/2 lines, rather than (n-1)/2. This time, as I said before, the left-hand term goes to zero, so the +1 doesn't come into play, and the summation does not get doubled. Hence the constant term is \sum_{m=0}^{\frac{n-4}{2}}4^m.

That gets you to the point where I provided the expressions. I assume you followed what I did after that to reach a closed-form expression for the summation using the identity I provided. Hope that helps! If I didn't explain it well, let me know and I'll try to clarify.

Josh

By the way, if it wasn't self-evident that b_0=0, you can either solve for it using the recursive relationship for b_n:

b_n=2b_{n-2}+b{n-1}

b_2=2b_0+b_1

1=2b_0+1

b_0=0

or you could simply consider that any matrix (including A) raised to the 0 power will result in the identity matrix, wherein all of the off-diagonal terms (i.e. the b's) are 0. Hence b_0=0.

Thanks a lot!

This is an amazing thread - thanks lemon14 and JC2!

This is an amazing thread - thanks lemon14 and JC2!

Thanks EB! It was a fun challenge trying to figure this one out.

I just looked back at this and realized something I should have seen the first time. First, let me rewrite the answers using powers of 2, rather than 4, so that the fraction in the exponent goes away:

odd: b_n=2^{n-2}+\frac{2}{3}\(2^{n-3}-1\)+1

even: b_n=2^{n-2}+\frac{1}{3}\(2^{n-2}-1\)

Now distribute the coefficient in front of the parentheses:

odd: b_n=2^{n-2}+\frac{2}{3}\(2^{n-3}\)+\frac13

even: b_n=2^{n-2}+\frac{1}{3}\(2^{n-2}\)-\frac13

Next take the 2 out of the numerator in the odd case and work it into the exponent (i.e. increment the exponent by 1 to account for it).

odd: b_n=2^{n-2}+\frac{1}{3}\(2^{n-2}\)+\frac13

even: b_n=2^{n-2}+\frac{1}{3}\(2^{n-2}\)-\frac13

Now combine like terms and factor out the \frac13.

odd: b_n=\frac{4\(2^{n-2})+1}{3}

even: b_n=\frac{4\(2^{n-2}\)-1}{3}

Next work the 4's into the exponent by incrementing it by 2 (since 4=2^2).

odd: b_n=\frac{2^n+1}{3}

even: b_n=\frac{2^n-1}{3}

Finally, since the two formulas only differ by a negative sign, just combine them into one:

\fbox{\color{Red}b_n=\frac{2^n-(-1)^n}{3}}

Much simpler!!

Or if you want to be really, REALLY concise:

b_n=\lfloor \frac{2^n}{3}\rceil

That notation means to round to the closest integer.