All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 An interesting matrix (Posted on 2015-11-05)
Let matrix A be the following:
```⌈1 1⌉
⌊1 0⌋
```
Explore the sequence A1, A2, A3, A4...

Explain the pattern that results.

 No Solution Yet Submitted by Jer No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution -- calculations by computer | Comment 1 of 3
The original matrix

1 1
1 0

can be considered to exhibit Fibonacci numbers 0, 1 and 2.

Successive powers of the matrix exhibit further Fibonacci numbers as noted:

2 1       F(3) F(2)
1 1       F(2) F(1)

3 2       F(4) F(3)
2 1       F(3) F(1)

5 3       F(5) F(4)
3 2       F(4) F(3)

8 5       F(6) F(5)
5 3       F(5) F(4)

13 8       F(7) F(6)
8 5       F(6) F(5)

21 13       F(8) F(7)
13  8       F(7) F(6)

34 21       F(9) F(8)
21 13       F(8) F(7)

55 34       F(10) F(9)
34 21       F(9)  F(8)

89 55       F(11) F(10)
55 34       F(10) F(9)

In general, A^n is

F(n + 1)      F(n)

F(n)       F(n - 1)

DefDbl A-Z
Dim crlf\$, matrix(2, 2)

Form1.Visible = True

Text1.Text = ""
crlf = Chr\$(13) + Chr\$(10)

matrix(1, 1) = 1
matrix(1, 2) = 1
matrix(2, 1) = 1
matrix(2, 2) = 0

For i = 1 To 9
a = matrix(1, 1) + matrix(2, 1)
b = matrix(1, 2) + matrix(2, 2)
c = matrix(1, 1)
d = matrix(1, 2)
matrix(1, 1) = a
matrix(1, 2) = b
matrix(2, 1) = c
matrix(2, 2) = d
Text1.Text = Text1.Text & a & Str(b) & "       " & "F(" & whichFib(a) & ") F(" & whichFib(b) & ")" & crlf
Text1.Text = Text1.Text & c & Str(d) & "       " & "F(" & whichFib(c) & ") F(" & whichFib(d) & ")" & crlf & crlf
Next

Text1.Text = Text1.Text & crlf & " done"

End Sub

Function whichFib(x)
wf = Log(x) / Log((1 + Sqr(5)) / 2)
whichFib = -Int(-wf) + 1 ' ceiling function, then plus 1
End Function

The whichFib() annotation was added, of course, after the pattern was observed.

The program calculates whichFib(1) as 1, which is a correct possibility, but to keep the sequence straight, in the output I overwrote with 2, the other correct possibility, in two places on the table.

Removing the matrix notation, in each iteration, and adding generation subscripts:

a(n) = a(n-1) + c(n-1) = a(n-1) + a(n-2)
b(n) = b(n-1) + d(n-1) = b(n-1) + b(n-2)
c(n) = a(n-1)
d(n) = b(n-1)

which explains the Fibonacci pattern.

 Posted by Charlie on 2015-11-05 10:06:29

 Search: Search body:
Forums (0)