Given triangle M as an infinite lower triangular matrix, there is some sequence prefaced with a "1" such that M*(seq prefaced with a 1) shifts the sequence to the left, deleting the "1", while the rest of the sequence remains the same. That seq is the Eigensequence of a triangle (defined without the prepended 1).
.
Example: The Eigensequence of Pascal's triangle is A000110 in Sloane's Encyclopedia of Integer Sequences: (1, 2, 5, 15, 52,...) = the Bell seq; since letting the Pascal matrix = M, then M*(1, 1, 2, 5, 15, 52,...) = (1, 2, 5, 15, 52,...).
.
Getting the Eigensequence. Simple. Place a "1" at the top of the triangle M, getting: (using the initial Pascal's triangle):
1
1;
1, 1;
1, 2, 1;
1, 3, 3, 1;
1, 4, 6, 4, 1;
...
= new triangle Q. Take successive powers of Q, shifting all terms into a vector which is (1, 1, 2, 5, 15, 52,...). Delete the initial 1 getting (1, 2, 5, 15, 52,...), = the Bell sequence which is the Eigensquence of Pascal's Triangle.
...
THEOREM: Given an infinite Toeplitz triangle with sequence S(n) in every column, we obtain the Eigensequence as before; with the additional property that in such a Toeplitz triangle, the Eigensequence is the INVERT transform of S(n).
...
Example: Given S(n) = (1, 2, 3, 4,...), our Toeplitz triangle =
1;
2, 1;
3, 2, 1;
4, 3, 2, 1;
... = M
We place a "1" at top, take powers, getting our left-shifted vector (even-indexed Fibonacci numbers after deleting the 1): (1, 3, 8 21, 55,...). So (1, 3, 8, 21,...) is the Eigensequence of the triangle and the INVERT transform of (1, 2, 3, 4,....), the natural numbers.
.
To obtain an Eigentriangle R which has row sums of the Eigensequence of triangle M, we take the row terms of M, multiplying pairwise by terms in its Eigensequence (prefaced with a 1). Thus, using the above triangle M and (1, 1, 3, 8, 21,...) our products are (1), [(2,1)*(1,1) = (2,1)], then [(3,2,1)*(1,1,3) = (3,2,3)];, then [(4,3,2,1)*(1,1,3,8) = (4,3,6,8)]; so our Eigentriangle R =
1;
2, 1;
3, 2, 3;
4, 3, 6, 8;
... = R
...which as you can see has row sums of (1, 3, 8, 21,...). Thus, R is the Eigentriangle of triangle M.
Thursday, January 19, 2012
Matrix generation of sequences
Observe the following infinite square production matrix:
1, 1, 0, 0, 0, 0,...
A, 0, 1, 0, 0, 0,...
B, 0, 0, 1, 0, 0,..
C, 0, 0, 0, 1, 0,...
D, 0, 0, 0, 0, 1,...
...
Say we have a finite (A,B,C) = (1, 1, 2). Then the g.f. (generating function) is:
1/(1-Ax-Bx^2-Cx^3) = 1/(1-x-x^2-2x^3) and the recursive relationship is:
a(n) = A*a(n-1) + B*a(n-2) + C *a(n-3).
The matrix generator is:
1, 1, 0
1, 0, 1
2, 0, 0
= M.
Any of these methods generates A077947: (1, 2, 5, 9, 18, 37, 73,...) as follows:
First, we plug in 1/(1-x-x^2-2x^3) into WolframAlpha, enter, and up comes the sequence.
By recursion, 18 = 1*9 + 1*5 + 2*2 = 9 + 5 = 4; or, a(n) = 1*a(n-1) + 1*a(n-2) * 2*a(n-3).
Or, let the Matrix = M, then take successive powers * the vector
[1
0
0]
...accessing top term; thus a(n) = M^n*[1,0,0], top term. Note that we extract the generating matrix M from the infinite square production matrix, such that M is an n*n matrix depending on the numbers of terms in (A,B,C...). That is, 3 in this case.
1, 1, 0, 0, 0, 0,...
A, 0, 1, 0, 0, 0,...
B, 0, 0, 1, 0, 0,..
C, 0, 0, 0, 1, 0,...
D, 0, 0, 0, 0, 1,...
...
Say we have a finite (A,B,C) = (1, 1, 2). Then the g.f. (generating function) is:
1/(1-Ax-Bx^2-Cx^3) = 1/(1-x-x^2-2x^3) and the recursive relationship is:
a(n) = A*a(n-1) + B*a(n-2) + C *a(n-3).
The matrix generator is:
1, 1, 0
1, 0, 1
2, 0, 0
= M.
Any of these methods generates A077947: (1, 2, 5, 9, 18, 37, 73,...) as follows:
First, we plug in 1/(1-x-x^2-2x^3) into WolframAlpha, enter, and up comes the sequence.
By recursion, 18 = 1*9 + 1*5 + 2*2 = 9 + 5 = 4; or, a(n) = 1*a(n-1) + 1*a(n-2) * 2*a(n-3).
Or, let the Matrix = M, then take successive powers * the vector
[1
0
0]
...accessing top term; thus a(n) = M^n*[1,0,0], top term. Note that we extract the generating matrix M from the infinite square production matrix, such that M is an n*n matrix depending on the numbers of terms in (A,B,C...). That is, 3 in this case.
Wednesday, September 1, 2010
Wednesday, August 25, 2010
Tuesday, August 24, 2010
INVERT transform
The basic links at OEIS, http://www.tinyurl.com/4zq4q showing the
arxiv article listed - by Bernstein and Sloane.
The operations are presented in this blog, by way of example: find the INVERT
transform of (1, 2, 3,..).
...
1. Given an offset of 1 for S(x) = (x + 2x^2 + 3x^3 + 4x^4 +...); we plug about 6 of such terms into Wolfram alpha with S(x) in the following:
INVERT transform = (1 / (1 - S(x)) - 1.
So we plug into the field: 1/(1 - x - 2x^2 - 3x^3 - 4x^4 - 5x^5), enter.
Then subtract 1 getting (x + 3x^2 + 8x^3 + 21x^4 + 55x^5 + ...) where the coefficients = the even indexed Fibonacci numbers (1, 3, 8, 21,...). Therefore, the INVERT transform of (1, 2, 3,...) = (1, 3, 8, 21, 55,...).
....
The reverse operation = the INVERTi transform and can be defined as
(-1 / (1 + S(x)) + 1; and in an operational mode, we enter into WolframAlpha:
-1 / (1 + x + 3x^2 + 8x^3 + 21x^4 + 55x^5), then enter.
Subtract 1, getting (x + 2x^2 + 3x^3 + 4x^4 + ...). Therefore, the INVERTi
transform of (1, 3, 8, 21,...) = (1, 2, 3,...).
...
A property of INVERT transforms (say, B(x) is the INVERT transform of A(x);
then we preface B(x) with a 1 = (1 + B(x)) . Then A(x) * (1 + B(x)) = B(x).
That is, the INVERT transform shifts to the left when prefaced with a 1 and "convolved" with A(x). Example using A(x) = (1, 2, 3,...) and B(x) = (1, 3, 8,..).
...
Again, using WolframAlpha, we plug in:
(x + 2x^2 + 3x^3 + 4x^4 + 5x^5) * (1 + x + 3x^2 + 8x^3 + 21x^4 + 55x^5 + ...).
getting (x + 3x^2 + 8x^3 + 21x^4).
Thus, (1, 1, 3, 8, 21, 55,....) has shifted to the left to (1, 3, 8, 21,...) when
convolved with (1, 2, 3,..).
arxiv article listed - by Bernstein and Sloane.
The operations are presented in this blog, by way of example: find the INVERT
transform of (1, 2, 3,..).
...
1. Given an offset of 1 for S(x) = (x + 2x^2 + 3x^3 + 4x^4 +...); we plug about 6 of such terms into Wolfram alpha with S(x) in the following:
INVERT transform = (1 / (1 - S(x)) - 1.
So we plug into the field: 1/(1 - x - 2x^2 - 3x^3 - 4x^4 - 5x^5), enter.
Then subtract 1 getting (x + 3x^2 + 8x^3 + 21x^4 + 55x^5 + ...) where the coefficients = the even indexed Fibonacci numbers (1, 3, 8, 21,...). Therefore, the INVERT transform of (1, 2, 3,...) = (1, 3, 8, 21, 55,...).
....
The reverse operation = the INVERTi transform and can be defined as
(-1 / (1 + S(x)) + 1; and in an operational mode, we enter into WolframAlpha:
-1 / (1 + x + 3x^2 + 8x^3 + 21x^4 + 55x^5), then enter.
Subtract 1, getting (x + 2x^2 + 3x^3 + 4x^4 + ...). Therefore, the INVERTi
transform of (1, 3, 8, 21,...) = (1, 2, 3,...).
...
A property of INVERT transforms (say, B(x) is the INVERT transform of A(x);
then we preface B(x) with a 1 = (1 + B(x)) . Then A(x) * (1 + B(x)) = B(x).
That is, the INVERT transform shifts to the left when prefaced with a 1 and "convolved" with A(x). Example using A(x) = (1, 2, 3,...) and B(x) = (1, 3, 8,..).
...
Again, using WolframAlpha, we plug in:
(x + 2x^2 + 3x^3 + 4x^4 + 5x^5) * (1 + x + 3x^2 + 8x^3 + 21x^4 + 55x^5 + ...).
getting (x + 3x^2 + 8x^3 + 21x^4).
Thus, (1, 1, 3, 8, 21, 55,....) has shifted to the left to (1, 3, 8, 21,...) when
convolved with (1, 2, 3,..).
Monday, July 5, 2010
Proof of Adamson's conjecture on palindromic continued fractions, re: A179238
Proof of Adamson's conjecture: Gary W. Adamson, re: A179238 in OEIS stating that :
a. given t = irrational Tan A, then if t = the convergent to an infinitely periodic palindromic continued fraction, then Tan 2A is rational; and the converse.
b. Tan 2A is rational when Tan A is rational iff, Tan A = t = the convergent to an infinitely periodic palindromic continued fraction.
Example: barover[a], with a = 1 getting [1,1,1,1,...] = .618....; with the inverse 1.618.... = t (either case) = Tan A.; where 1.618... is irrational.. If t = .618...then Tan 2A = 2.0. If t = 1.618..., then Tan 2A = -2.
...
We will present the sections of the proof then put the separate components together.
Part A: Given t = Tan A, then the double angle 2A triangle hs lets of 2t and t^2-1, with hyptenuse t^2+1.
...
The key step here is the relationship Q = t - 1/t = rational; example 1.618... - .618...= 1.
In order for t to be irrational but Tan 2A to be rational, t - 1/t = Q must be rational (to be shown); but for now continuing with this algrbra,; we have
Q = 1 - 1/t, then Qt = t^2 - 1, and
2t * (QT) = 2t * (t^2 - 1); with 2t / (t^2-1) = 2t / Qt = 2/Q; (and Q is rational).
...
Alternatively, using Tan 2A = 2TanA / (1 - Tan^2 A,) , let t = Tan A, say phi^(-3).
Then Tan 2A = 2*(phi^-3) / (1 - phi^-3) =
2 / (phi^3 - phi^(-3); fulfilling our required identity such that phi^3 - phi^(-3) = 4, since
phi^3 = 4.236...; where .236...= [4,4,4,4,4,4,....] ; palindromic
...Thus, a specific case. of Tan 2A = 2 Tan A / (1 - Tan^2 A), where Tan A = phi^3 or it's inverse.
...
Next, we investigate Part B:
States that t - 1/t must be rational, and looking at the "tail" of an infinitely periodic continued fraction (refer to Wolfram's Mathworld); the "tail" using the formula, and applying to barover [1,2,3] = [1,2,3,1,2,3,1,2,3,...] this is not palindromic and is thus a counter example. The "tail" becomes (2x + 7 / (3x + 10) setting this = to x, getting 3x^2 + 8x - 7, the roots to this being the convergent to barover [1,2,3].
...
We can straightaway obtain the formula 3x^2 + 8x - 7 by writing the partial quotients of [1,2,3] underneath as follows:
1,.......2,........3
1/1 2/3 7/10.
We put 2/3 and 7/10 into a 2x2 format as:
2, 7
3, 10 and perform the following operation such that lower left term (3) = a, upper right = c;
and (lower right - upper left) = b, or f(x), (a,b,c) = ax^2 + bx - c = 0 or
3x^2 + 8x - 7 = 0, and we note that a is not equal to c or 3 is not equal to 7.
...
Next, it follows that in constants of the form used in our conjecture c - 1/c = rational; the corresponding quadratic equation must be such that a must = c.; this being the case, dividing through by (a, c) we obtain an equation of the form x^2 - bx - 1 = 0, where b is rational.
This equation is the characteristic polynomial for an infinitely periodic, palindromic continued fraction, equavalent to the statement in the above 2x2 format that the lower left term must equal the upper right term. In this case 3 is not equal to 7, and the roots are not of the form t - 1/t = rational.
....
Part C. In order for the lower left term to equal the upper right term, we again refer to the "tail" of an infinitely periodic continued fraction which in the case of barover[1,2,3] =
2x + 7 / (3x+10), then setting this to x, we get 3x^2 + 8x - 7 = 0; again 3 is not equal to 7.
We need the tail of the form where upper right and lower left terms are equal, in other words,
in the convergents to [1, 2, 3] we have the partial quotients underneath:
1,.......2,.......7 and
1,.......3,......10. since [1,2,3] = 7/10 and the partial quotient to the left = 2/3.
...
Part D. We refer to Mathworld "Continued fraction", theorem 30 and 31 which state that:
pn / p(n-1) = [an, a(n-1), ....ao] = (30) and
qn / (q(n-1) = [an....a1]................=(31)
...In other words, (30) applies to the reversal of [a,b,c] saying we start with an, then procede to a0. For example, given [1,2,3,4] , theorem 30 uses [4, 3, 2, 1]. Where [1,2,3,4] = 30/43 as follows:
1,.......2,.......7,........30
1,.......3,......10,......43
...then reverse using [4, 3, 2, 1] = obtaining
1,.......3,.......7,.......10
4,......13,.....30,.....43.; so in essence, theorem 30 switches the position of the upper left and lower right terms, with the 7 and 43 terms invariant.
...
Now if the reversal of [a,b,c] remains invariant and thus the upper right and lower left terms are unchanged, this could only occur if the reversal is palindromic, such as [1, 2, 2, 1] where our convergents are
1,....2,......5,......7
1,....3,......7,.....10.
Thus only in a palindromic continued fraction is the lower left term = to the upper right.
Part E.
It follows from the formula of the "tail" say given (using different a,b,c,...):
we set x =( ax + b) / (cx + d); but again changing the usage of our (a,b,c,...) the quadratic formula for the tail if the (upper right = lower left) condition holds must be such that in
ax^2 + bx - c, a must = c. where a,b,c are all rational.
...But only when in this quadratic, a = c does the result hold (dividing through by a = c), we obtain
x^2 - bx - 1 = 0 (with an allowance for changing signs); and if b is rational, then we have our necessary equation with roots t and 1/t such that for example 1.618... - .618 = 1, rational, or
t - 1/t is rational, but t is irrational.
...
Combining all of the steps, Q.E.D. especially noting the key step "upper right = lower left term";
we have shown that in given t irrational, t must be the convergent of an infinitely periodic, palindromic continued fraction in order that angle 2A is rational. Of course, if Tan 2A is rational, t can be rational; but our conjecture only applies to the case in which Tan 2A is rational and t (Tan A) is irrational. The converse of the conjecture is also true.
a. given t = irrational Tan A, then if t = the convergent to an infinitely periodic palindromic continued fraction, then Tan 2A is rational; and the converse.
b. Tan 2A is rational when Tan A is rational iff, Tan A = t = the convergent to an infinitely periodic palindromic continued fraction.
Example: barover[a], with a = 1 getting [1,1,1,1,...] = .618....; with the inverse 1.618.... = t (either case) = Tan A.; where 1.618... is irrational.. If t = .618...then Tan 2A = 2.0. If t = 1.618..., then Tan 2A = -2.
...
We will present the sections of the proof then put the separate components together.
Part A: Given t = Tan A, then the double angle 2A triangle hs lets of 2t and t^2-1, with hyptenuse t^2+1.
...
The key step here is the relationship Q = t - 1/t = rational; example 1.618... - .618...= 1.
In order for t to be irrational but Tan 2A to be rational, t - 1/t = Q must be rational (to be shown); but for now continuing with this algrbra,; we have
Q = 1 - 1/t, then Qt = t^2 - 1, and
2t * (QT) = 2t * (t^2 - 1); with 2t / (t^2-1) = 2t / Qt = 2/Q; (and Q is rational).
...
Alternatively, using Tan 2A = 2TanA / (1 - Tan^2 A,) , let t = Tan A, say phi^(-3).
Then Tan 2A = 2*(phi^-3) / (1 - phi^-3) =
2 / (phi^3 - phi^(-3); fulfilling our required identity such that phi^3 - phi^(-3) = 4, since
phi^3 = 4.236...; where .236...= [4,4,4,4,4,4,....] ; palindromic
...Thus, a specific case. of Tan 2A = 2 Tan A / (1 - Tan^2 A), where Tan A = phi^3 or it's inverse.
...
Next, we investigate Part B:
States that t - 1/t must be rational, and looking at the "tail" of an infinitely periodic continued fraction (refer to Wolfram's Mathworld); the "tail" using the formula, and applying to barover [1,2,3] = [1,2,3,1,2,3,1,2,3,...] this is not palindromic and is thus a counter example. The "tail" becomes (2x + 7 / (3x + 10) setting this = to x, getting 3x^2 + 8x - 7, the roots to this being the convergent to barover [1,2,3].
...
We can straightaway obtain the formula 3x^2 + 8x - 7 by writing the partial quotients of [1,2,3] underneath as follows:
1,.......2,........3
1/1 2/3 7/10.
We put 2/3 and 7/10 into a 2x2 format as:
2, 7
3, 10 and perform the following operation such that lower left term (3) = a, upper right = c;
and (lower right - upper left) = b, or f(x), (a,b,c) = ax^2 + bx - c = 0 or
3x^2 + 8x - 7 = 0, and we note that a is not equal to c or 3 is not equal to 7.
...
Next, it follows that in constants of the form used in our conjecture c - 1/c = rational; the corresponding quadratic equation must be such that a must = c.; this being the case, dividing through by (a, c) we obtain an equation of the form x^2 - bx - 1 = 0, where b is rational.
This equation is the characteristic polynomial for an infinitely periodic, palindromic continued fraction, equavalent to the statement in the above 2x2 format that the lower left term must equal the upper right term. In this case 3 is not equal to 7, and the roots are not of the form t - 1/t = rational.
....
Part C. In order for the lower left term to equal the upper right term, we again refer to the "tail" of an infinitely periodic continued fraction which in the case of barover[1,2,3] =
2x + 7 / (3x+10), then setting this to x, we get 3x^2 + 8x - 7 = 0; again 3 is not equal to 7.
We need the tail of the form where upper right and lower left terms are equal, in other words,
in the convergents to [1, 2, 3] we have the partial quotients underneath:
1,.......2,.......7 and
1,.......3,......10. since [1,2,3] = 7/10 and the partial quotient to the left = 2/3.
...
Part D. We refer to Mathworld "Continued fraction", theorem 30 and 31 which state that:
pn / p(n-1) = [an, a(n-1), ....ao] = (30) and
qn / (q(n-1) = [an....a1]................=(31)
...In other words, (30) applies to the reversal of [a,b,c] saying we start with an, then procede to a0. For example, given [1,2,3,4] , theorem 30 uses [4, 3, 2, 1]. Where [1,2,3,4] = 30/43 as follows:
1,.......2,.......7,........30
1,.......3,......10,......43
...then reverse using [4, 3, 2, 1] = obtaining
1,.......3,.......7,.......10
4,......13,.....30,.....43.; so in essence, theorem 30 switches the position of the upper left and lower right terms, with the 7 and 43 terms invariant.
...
Now if the reversal of [a,b,c] remains invariant and thus the upper right and lower left terms are unchanged, this could only occur if the reversal is palindromic, such as [1, 2, 2, 1] where our convergents are
1,....2,......5,......7
1,....3,......7,.....10.
Thus only in a palindromic continued fraction is the lower left term = to the upper right.
Part E.
It follows from the formula of the "tail" say given (using different a,b,c,...):
we set x =( ax + b) / (cx + d); but again changing the usage of our (a,b,c,...) the quadratic formula for the tail if the (upper right = lower left) condition holds must be such that in
ax^2 + bx - c, a must = c. where a,b,c are all rational.
...But only when in this quadratic, a = c does the result hold (dividing through by a = c), we obtain
x^2 - bx - 1 = 0 (with an allowance for changing signs); and if b is rational, then we have our necessary equation with roots t and 1/t such that for example 1.618... - .618 = 1, rational, or
t - 1/t is rational, but t is irrational.
...
Combining all of the steps, Q.E.D. especially noting the key step "upper right = lower left term";
we have shown that in given t irrational, t must be the convergent of an infinitely periodic, palindromic continued fraction in order that angle 2A is rational. Of course, if Tan 2A is rational, t can be rational; but our conjecture only applies to the case in which Tan 2A is rational and t (Tan A) is irrational. The converse of the conjecture is also true.
Thursday, March 25, 2010
Ternary Gray code
Enter "Gray code conversion rules" into Google to bring up the general rules; following rules in A147995 in OEIS: http://www.tinyurl.com/4zq4q
then, following the reflection principle for Gray code k, we write out (say k=3) 0,1,2; 2,0,1; 1,2,0; ...in the right column; i.e. we write each term in the series once, then for the next subset of 3, we repeat the last term recorded, or "reflect" it.
...0
...1
...2;
now reflect, starting the series again (2, then 0, 1,...):
...2,
...0,
...1;
now for the next subset we reflect the "1" getting
...1
...2 (continuing with 0,1,2, etc.)
Now for the next column going to the left, we mark down each term 3 times; and the next column after that (column 3), 9 times, so that each term in the series 0,1,2 (and generally, 0,1,2,3,...for any k) is marked down k^0, k^1, k^2,....times along with the reflection principle. Thus, for Ternary Gray code we obtain:
000
001
002
012
010
011
021
022
020
120
121
122
102
101
100
110
111
112
...
then, following the reflection principle for Gray code k, we write out (say k=3) 0,1,2; 2,0,1; 1,2,0; ...in the right column; i.e. we write each term in the series once, then for the next subset of 3, we repeat the last term recorded, or "reflect" it.
...0
...1
...2;
now reflect, starting the series again (2, then 0, 1,...):
...2,
...0,
...1;
now for the next subset we reflect the "1" getting
...1
...2 (continuing with 0,1,2, etc.)
Now for the next column going to the left, we mark down each term 3 times; and the next column after that (column 3), 9 times, so that each term in the series 0,1,2 (and generally, 0,1,2,3,...for any k) is marked down k^0, k^1, k^2,....times along with the reflection principle. Thus, for Ternary Gray code we obtain:
000
001
002
012
010
011
021
022
020
120
121
122
102
101
100
110
111
112
...
Subscribe to:
Posts (Atom)