| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
The Fibonacci polynomials, F (x) can be defined as follows:
n
F (x)= 1, F (x) = x, F (x) = x F (x) + F (x) .
1 2 n+1 n n-1
It is known that if d|n (d divides n), then F (x)|F (x).
d n
I was wondering if that would account for the complete factorization
of the Fibonacci polynomials. Apparently it doesn't. Here's some data.
Can anyone come up with a formula for the complete factorization of
F (x)? In particular, if p is a prime, is F (x) irreducible?
n p
2
F (x) = x + 1
3
2
Factors = x + 1
3
F (x) = x + 2 x
4
2
Factors = x (x + 2)
4 2
F (x) = x + 3 x + 1
5
4 2
Factors = x + 3 x + 1
5 3
F (x) = x + 4 x + 3 x
6
2 2
Factors = x (x + 1) (x + 3)
6 4 2
F (x) = x + 5 x + 6 x + 1
7
6 4 2
Factors = x + 5 x + 6 x + 1
7 5 3
F (x) = x + 6 x + 10 x + 4 x
8
2 4 2
Factors = x (x + 2) (x + 4 x + 2)
8 6 4 2
F (x) = x + 7 x + 15 x + 10 x + 1
9
2 6 4 2
Factors = (x + 1) (x + 6 x + 9 x + 1)
9 7 5 3
F (x) = x + 8 x + 21 x + 20 x + 5 x
10
4 2 4 2
Factors = x (x + 3 x + 1) (x + 5 x + 5)
10 8 6 4 2
F (x) = x + 9 x + 28 x + 35 x + 15 x + 1
11
10 8 6 4 2
Factors = x + 9 x + 28 x + 35 x + 15 x + 1
11 9 7 5 3
F (x) = x + 10 x + 36 x + 56 x + 35 x + 6 x
12
2 2 2 4 2
Factors = x (x + 1) (x + 2) (x + 3) (x + 4 x + 1)
12 10 8 6 4 2
F (x) = x + 11 x + 45 x + 84 x + 70 x + 21 x + 1
13
12 10 8 6 4 2
Factors = x + 11 x + 45 x + 84 x + 70 x + 21 x + 1
13 11 9 7 5 3
F (x) = x + 12 x + 55 x + 120 x + 126 x + 56 x + 7 x
14
6 4 2 6 4 2
Factors = x (x + 5 x + 6 x + 1) (x + 7 x + 14 x + 7)
14 12 10 8 6 4 2
F (x) = x + 13 x + 66 x + 165 x + 210 x + 126 x + 28 x + 1
15
2 4 2 8 6 4 2
Factors = (x + 1) (x + 3 x + 1) (x + 9 x + 26 x + 24 x + 1)
15 13 11 9 7 5 3
F (x) = x + 14 x + 78 x + 220 x + 330 x + 252 x + 84 x + 8 x
16
2 4 2 8 6 4 2
Factors = x (x + 2) (x + 4 x + 2) (x + 8 x + 20 x + 16 x + 2)
16 14 12 10 8 6 4 2
F (x) = x + 15 x + 91 x + 286 x + 495 x + 462 x + 210 x + 36 x + 1
17
16 14 12 10 8 6 4 2
Factors = x + 15 x + 91 x + 286 x + 495 x + 462 x + 210 x + 36 x + 1
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 94.1 | AURORA::HALLYB | Tue Jul 17 1984 13:02 | 47 | ||
Let me define the following infinite matrix (where row and column numbering
are both zero-origin):
> The 0-th column is all 1s.
> The 0-th row is alternating 1s and 0s.
> Every column topped by a 0 is all 0s.
> All remaining entries are filled in by adding the number above with the
number two positions to the left.
What you get looks like:
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 ...
1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 ...
1 0 3 0 6 0 10 0 15 0 21 0 28 0 36 0 45 ...
1 0 4 0 10 0 20 0 35 0 56 0 84 0 120 0 165
1 0 5 0 15 0 35 0 70 0 126 0 210 0 330 ...
1 0 6 0 21 0 56 0 126 0 252 0 462 ...
1 0 7 0 28 0 84 0 210 0 462 0 ...
1 0 8 0 36 0 120 0 330 0 792 ...
1 0 9 0 45 0 165 0 495 0 ...
Reading the matrix along the diagonals (up and to the right) you get exactly
the coefficients of the Fibonacci polynomials. So, this is sort of a
"Pascal's triangle" for Fibonacci polynomials. As with Pascal's, there are
a number of interesting properties of this "triangle":
1
1 0
1 0 1
1 0 2 0
1 0 3 0 1
1 0 4 0 3 0
1 0 5 0 6 0 1
1 0 6 0 10 0 4 0
> Summing the coeffiecients of any row gets you ... what?
> The "triangle" is symmetric down the center except for those columns of 0s.
Exercise: How many more similarities are there?
Conjecture: All numbers beyond (column 3, row 3) are composite.
John
| |||||
| 94.2 | METOO::YARBROUGH | Wed Jul 18 1984 10:43 | 8 | ||
The numbers beyond (column 3, row 3) are certainly composite: they are the binomial coefficients C(n,k) where n-k >= 3, or n!/(k!)(n-k)! which is always an integer and, since formed by multiplying k>=3 consecutive (thus relatively prime) integers, always has at least two distinct prime divisors. Lynn Yarbrough | |||||
| 94.3 | HARE::STAN | Thu Jul 26 1984 01:48 | 269 | ||
Here's an expanded list, with factors of F through F .
3 29
2
F (x) = x + 1
3
2
Factors = x + 1
3
F (x) = x + 2 x
4
2
Factors = x (x + 2)
4 2
F (x) = x + 3 x + 1
5
4 2
Factors = x + 3 x + 1
5 3
F (x) = x + 4 x + 3 x
6
2 2
Factors = x (x + 1) (x + 3)
6 4 2
F (x) = x + 5 x + 6 x + 1
7
6 4 2
Factors = x + 5 x + 6 x + 1
7 5 3
F (x) = x + 6 x + 10 x + 4 x
8
2 4 2
Factors = x (x + 2) (x + 4 x + 2)
8 6 4 2
F (x) = x + 7 x + 15 x + 10 x + 1
9
2 6 4 2
Factors = (x + 1) (x + 6 x + 9 x + 1)
9 7 5 3
F (x) = x + 8 x + 21 x + 20 x + 5 x
10
4 2 4 2
Factors = x (x + 3 x + 1) (x + 5 x + 5)
10 8 6 4 2
F (x) = x + 9 x + 28 x + 35 x + 15 x + 1
11
10 8 6 4 2
Factors = x + 9 x + 28 x + 35 x + 15 x + 1
11 9 7 5 3
F (x) = x + 10 x + 36 x + 56 x + 35 x + 6 x
12
2 2 2 4 2
Factors = x (x + 1) (x + 2) (x + 3) (x + 4 x + 1)
12 10 8 6 4 2
F (x) = x + 11 x + 45 x + 84 x + 70 x + 21 x + 1
13
12 10 8 6 4 2
Factors = x + 11 x + 45 x + 84 x + 70 x + 21 x + 1
13 11 9 7 5 3
F (x) = x + 12 x + 55 x + 120 x + 126 x + 56 x + 7 x
14
6 4 2 6 4 2
Factors = x (x + 5 x + 6 x + 1) (x + 7 x + 14 x + 7)
14 12 10 8 6 4 2
F (x) = x + 13 x + 66 x + 165 x + 210 x + 126 x + 28 x + 1
15
2 4 2 8 6 4 2
Factors = (x + 1) (x + 3 x + 1) (x + 9 x + 26 x + 24 x + 1)
15 13 11 9 7 5 3
F (x) = x + 14 x + 78 x + 220 x + 330 x + 252 x + 84 x + 8 x
16
2 4 2 8 6 4 2
Factors = x (x + 2) (x + 4 x + 2) (x + 8 x + 20 x + 16 x + 2)
16 14 12 10 8 6 4 2
F (x) = x + 15 x + 91 x + 286 x + 495 x + 462 x + 210 x + 36 x + 1
17
16 14 12 10 8 6 4 2
Factors = x + 15 x + 91 x + 286 x + 495 x + 462 x + 210 x + 36 x
+ 1
17 15 13 11 9 7 5 3
F (x) = x + 16 x + 105 x + 364 x + 715 x + 792 x + 462 x + 120 x
18
+ 9 x
2 2 6 4 2 6 4 2
Factors = x (x + 1) (x + 3) (x + 6 x + 9 x + 1) (x + 6 x + 9 x + 3)
18 16 14 12 10 8 6
F (x) = x + 17 x + 120 x + 455 x + 1001 x + 1287 x + 924 x
19
4 2
+ 330 x + 45 x + 1
18 16 14 12 10 8 6
Factors = x + 17 x + 120 x + 455 x + 1001 x + 1287 x + 924 x
4 2
+ 330 x + 45 x + 1
19 17 15 13 11 9 7
F (x) = x + 18 x + 136 x + 560 x + 1365 x + 2002 x + 1716 x
20
5 3
+ 792 x + 165 x + 10 x
2 4 2 4 2
Factors = x (x + 2) (x + 3 x + 1) (x + 5 x + 5)
8 6 4 2
(x + 8 x + 19 x + 12 x + 1)
20 18 16 14 12 10 8
F (x) = x + 19 x + 153 x + 680 x + 1820 x + 3003 x + 3003 x
21
6 4 2
+ 1716 x + 495 x + 55 x + 1
2 6 4 2
Factors = (x + 1) (x + 5 x + 6 x + 1)
12 10 8 6 4 2
(x + 13 x + 64 x + 146 x + 148 x + 48 x + 1)
21 19 17 15 13 11 9
F (x) = x + 20 x + 171 x + 816 x + 2380 x + 4368 x + 5005 x
22
7 5 3
+ 3432 x + 1287 x + 220 x + 11 x
10 8 6 4 2
Factors = x (x + 9 x + 28 x + 35 x + 15 x + 1)
10 8 6 4 2
(x + 11 x + 44 x + 77 x + 55 x + 11)
22 20 18 16 14 12 10
F (x) = x + 21 x + 190 x + 969 x + 3060 x + 6188 x + 8008 x
23
8 6 4 2
+ 6435 x + 3003 x + 715 x + 66 x + 1
22 20 18 16 14 12 10
Factors = x + 21 x + 190 x + 969 x + 3060 x + 6188 x + 8008 x
8 6 4 2
+ 6435 x + 3003 x + 715 x + 66 x + 1
23 21 19 17 15 13 11
F (x) = x + 22 x + 210 x + 1140 x + 3876 x + 8568 x + 12376 x
24
9 7 5 3
+ 11440 x + 6435 x + 2002 x + 286 x + 12 x
2 2 2 4 2 4 2
Factors = x (x + 1) (x + 2) (x + 3) (x + 4 x + 1) (x + 4 x + 2)
8 6 4 2
(x + 8 x + 20 x + 16 x + 1)
24 22 20 18 16 14 12
F (x) = x + 23 x + 231 x + 1330 x + 4845 x + 11628 x + 18564 x
25
10 8 6 4 2
+ 19448 x + 12870 x + 5005 x + 1001 x + 78 x + 1
4 2 20 18 16 14 12
Factors = (x + 3 x + 1) (x + 20 x + 170 x + 800 x + 2275 x
10 8 6 4 2
+ 4003 x + 4280 x + 2605 x + 775 x + 75 x + 1)
25 23 21 19 17 15 13
F (x) = x + 24 x + 253 x + 1540 x + 5985 x + 15504 x + 27132 x
26
11 9 7 5 3
+ 31824 x + 24310 x + 11440 x + 3003 x + 364 x + 13 x
12 10 8 6 4 2
Factors = x (x + 11 x + 45 x + 84 x + 70 x + 21 x + 1)
12 10 8 6 4 2
(x + 13 x + 65 x + 156 x + 182 x + 91 x + 13)
26 24 22 20 18 16 14
F (x) = x + 25 x + 276 x + 1771 x + 7315 x + 20349 x + 38760 x
27
12 10 8 6 4 2
+ 50388 x + 43758 x + 24310 x + 8008 x + 1365 x + 91 x + 1
2 6 4 2
Factors = (x + 1) (x + 6 x + 9 x + 1)
18 16 14 12 10 8 6 4
(x + 18 x + 135 x + 546 x + 1287 x + 1782 x + 1386 x + 540 x
2
+ 81 x + 1)
27 25 23 21 19 17 15
F (x) = x + 26 x + 300 x + 2024 x + 8855 x + 26334 x + 54264 x
28
13 11 9 7 5 3
+ 77520 x + 75582 x + 48620 x + 19448 x + 4368 x + 455 x + 14 x
2 6 4 2 6 4 2
Factors = x (x + 2) (x + 5 x + 6 x + 1) (x + 7 x + 14 x + 7)
12 10 8 6 4 2
(x + 12 x + 53 x + 104 x + 86 x + 24 x + 1)
28 26 24 22 20 18 16
F (x) = x + 27 x + 325 x + 2300 x + 10626 x + 33649 x + 74613 x
29
14 12 10 8 6 4 2
+ 116280 x + 125970 x + 92378 x + 43758 x + 12376 x + 1820 x + 105 x
+ 1
28 26 24 22 20 18 16
Factors = x + 27 x + 325 x + 2300 x + 10626 x + 33649 x + 74613 x
14 12 10 8 6 4 2
+ 116280 x + 125970 x + 92378 x + 43758 x + 12376 x + 1820 x + 105 x
+ 1
| |||||
| 94.4 | HARE::STAN | Thu Jul 26 1984 04:52 | 60 | ||
The following tabulation may be of some help. (Compare against the previous response to figure out what it means.) Note the inclusion/exclusion principle at work for the known factors. F2 = x^1 F3 = x^2 (1 1) F4 = F2 x^2 (1 2) F5 = x^4 (1 3 1) F6 = F2 F3 x^2 (1 3) F7 = x^6 (1 5 6 1) F8 = F4 x^4 (1 4 2) F9 = F3 x^6 (1 6 9 1) F10 = F2 F5 x^4 (1 5 5) F11 = x^10 (1 9 28 35 15 1) F12 = F4 F6 / F2 x^4 (1 4 1) F13 = x^12 (1 11 45 84 70 21 1) F14 = F2 F7 x^6 (1 7 14 7) F15 = F3 F5 x^8 (1 9 26 24 1) F16 = F8 x^8 (1 8 20 16 2) F17 = x^16 (1 15 91 286 495 462 210 36 1) F18 = F6 F9 / F3 x^6 (1 6 9 3) F19 = x^18 (1 17 120 455 1001 1287 924 330 45 1) F20 = F4 F10 / F2 x^8 (1 8 19 12 1) F21 = F3 F7 x^12 (1 13 64 146 148 48 1) F22 = F2 F11 x^10 (1 11 44 77 55 11) F23 = x^22 (1 21 190 969 3060 6188 8008 6435 3003 715 66 1) F24 = F8 F12 / F4 x^8 (1 8 20 16 1) F25 = F5 x^20 (1 20 170 800 2275 4003 4280 2605 775 75 1) F26 = F2 F13 x^12 (1 13 65 156 182 91 13) F27 = F9 x^18 (1 18 135 546 1287 1782 1386 540 81 1) F28 = F4 F14 / F2 x^12 (1 12 53 104 86 24 1) F29 = x^28 (1 27 325 2300 10626 33649 74613 116280 125970 92378 43758 12376 1820 105 1) | |||||
| 94.5 | HARE::STAN | Tue Aug 07 1984 22:41 | 35 | ||
Relationship Between Fibonacci Polynomials
and Chebyshev Polynomials of the 2nd kind
cos nt can be expanded out in terms of cos t. Let cos t = x, then
T (x) = cos nt is a polynomial in x of degree n. These are known
n
as the Chebyshev (Tchebychev) Polynomials of the first kind.
sin(n+1)t
Similarly, --------- = U (x) is also a polynomial of degree n
sin t n
in x = cos t. These polynomials are known as the Chebyshev polynomials
of the second kind.
If F (x) denotes the nth Fibonacci polynomial, then we have
n
-n
F (x) = i U (ix/2) .
n+1 n
Whether this has any application to the given problem, I don't know.
I \do/ know that a hell of a lot is known about Chebyshev polynomials.
References
----------
Polya and Szego, Problems and Theorems in Analysis, vol II, Springer-Verlag,
New York: 1976. page 71.
V. E. Hoggatt, Jr. and D. A. Lind, The Heights of Fibonacci Polynomials and
an Associated Function, The Fibonacci Quarterly, 5(1967)141-152.
| |||||