OFFSET
0,1
COMMENTS
GENERAL EXPLANATION OF TERMS AND CONCEPTS: (Start)
I. Let the term "transform" generally mean the operation of summing the products of the ascending numbers of a sequence and numbers in the j-th row of an m-nomial triangle (i.e., triangle of m-nomial coefficients, T(j,k)), thus generating a new sequence for each m as j increases {j=0..inf.}. Further, let T(0,0) be the top entry (0th row, 0th column) in an m-nomial triangle, where m >= 2 (m=2 being Pascal's triangle, m=3 the trinomial triangle, etc.) and {k=0..(m-1)*j} for row j.
II. In this entry, the sequence is the Fibonacci numbers (A000045), starting with F(1)=1. So for example, the pentanomial (m=5) transform of the Fibonacci numbers is {1, 12, 193, 3149, 51410, ...} because {1*1} = 1 when j=0 (transform of row 0); {1*1 + 1*1 + 1*2 + 1*3 + 1*5} = 12 when j=1 (transform of row 1); {1*1 + 2*1 + 3*2 + 4*3 + 5*5 + 4*8 + 3*13 + 2*21 + 1*34} = 193 when j=2 (transform of row 2), ad infinitum.
III. Let T'<m*> denote the entire sequence for the m-nomial transform of the Fibonacci numbers. So for example, T'<4*> is {1, 7, 65, 615, 5825, ...). Further, let T'<m>(n'') denote the transform at n''. So for example, when n''=3: T'<4>(3)=615.
IV. Every m-nomial transform of Fibonacci numbers can be generated using the table below (presented in three columns: a'', b'', and c''; see "Example" section) and its expansion, both with and without internal recurrence (see "Formula" section for expanded form).
V. Coefficients a'', b'' and c'' for row m (corresponding to the m-nomial triangle, the initial row being m=2) are used to find T'<m*> and T'<m>(n''), applying the following equation:
VI. GENERAL M-NOMIAL TRANSFORM EQUATION: T'<m>(n'') = a''*T'<m>(n''-1) + b''*(sum_T'<m>(i)) {i=0..(n''-2); n''>=2} - c''.
(Given: T'<m>(0)=1)
See "Example" section for T'<5*> (pentanomial transform: using row m=5 in table for a'', b'' and c''). (End)
FORMULA
I. EXPANSION FORMULAS without internal recurrence [corresponding table columns noted]:
a(n) = A000032(m+1)-2 when n == 0 (mod 3) [corresponds to column a'' in table].
a(n) = A000032(m-1) when n == 1 (mod 6) [column b'', even m].
a(n) = A000032(m-1)-2 when n == 4 (mod 6) [column b'', odd m].
a(n) = A000045(m)-1 when n == 2 (mod 3) [column c''].
II. EXPANSION FORMULAS with internal recurrence:
a(n) = 2*a(n-3) + a(n-9), n >= 9, when n == 0 (mod 3) [corresponds to column a'' in table].
a(n) = a(n-4) - a(n-3), n >= 4, when n == 1 (mod 3) [column b''].
a(n) = A000045(m)-1 when n == 2 (mod 3) [column c''].
EXAMPLE
I. COEFFICIENT TABLE (initial row: m=2)
m a" b" c"
2 2 1 0
3 5 1 1
4 9 4 2
5 16 5 4
6 27 11 7
7 45 16 12
8 74 29 20
9 121 45 33
10 197 76 54
11 320 121 88
12 519 199 143
13 841 320 232
14 1362 521 376
II. EXAMPLES OF EXPANSION FORMULAS for a(n):
a(12) = 27: (m=6; 12 == 0 (mod 3). A000032(7)-2 = 27, 2*16-5 = 27).
a(19) = 29: (m=8; 19 == 1 (mod 6). A000032(7) = 29, 45-16 = 29).
a(22) = 45: (m=9; 22 == 4 (mod 6). A000032(8)-2 = 45, 74-29 = 45).
a(23) = 33: (m=9; 23 == 2 (mod 3). A000045(9)-1 = 33).
III. EXAMPLE OF M-NOMIAL TRANSFORM USING GENERAL EQUATION, FOR T'<5*> (pentanomial transform -- m=5; a''=16, b''=5, c''=4. See "Comments" for explanation):
T'<5>(0) = 1 (given);
T'<5>(1) = 12: [16*T'<5>(0) - 4] = [16*1 - 4] = 12.
T'<5>(2) = 193: [16*T'<5>(1) + 5*T'<5>(0) - 4] = [16*12 + 5*1 - 4] = 193.
T'<5>(3) = 3149: [16*T'<5>(2) + 5*(T'<5>(1) + T'<5>(0)) - 4] = [16*193 + 5*(12+1) - 4] = 3149.
T'<5>(4) = 51410: [16*T'<5>(3) + 5*(T'<5>(2) + T'<5>(1) + T'<5>(0)) - 4] = [16*3149 + 5*(193+12+1) - 4] = 51410.
Therefore T'<5*> = {1, 12, 193, 3149, 51410, ...}.
CROSSREFS
KEYWORD
nonn
AUTHOR
Bob Selcoe, Jun 11 2014
STATUS
approved