Check out some similar questions!

lemon14 · Oct 29, 2011, 11:43 AM

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}$ ?

lemon14 · Oct 29, 2011, 11:46 AM

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. :|

jcaron2 · Oct 31, 2011, 08:51 AM

Originally Posted by lemon14

$\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$$

lemon14 · Oct 31, 2011, 12:25 PM

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.

jcaron2 · Oct 31, 2011, 02:15 PM

Originally Posted by lemon14

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

jcaron2 · Oct 31, 2011, 02:34 PM

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$ .

lemon14 · Nov 1, 2011, 11:26 AM

Thanks a lot!

ebaines · Nov 1, 2011, 04:23 PM

This is an amazing thread - thanks lemon14 and JC2!

jcaron2 · Nov 1, 2011, 07:36 PM

Originally Posted by ebaines

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!!

jcaron2 · Nov 1, 2011, 07:49 PM

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.