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

Home > Numbers > Sequences
An interesting matrix (Posted on 2015-11-05) Difficulty: 3 of 5
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 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)


Private Sub Form_Load()
 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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information