A105809 Riordan array (1/(1 - x - x^2), x/(1 - x)).

1, 1, 1, 2, 2, 1, 3, 4, 3, 1, 5, 7, 7, 4, 1, 8, 12, 14, 11, 5, 1, 13, 20, 26, 25, 16, 6, 1, 21, 33, 46, 51, 41, 22, 7, 1, 34, 54, 79, 97, 92, 63, 29, 8, 1, 55, 88, 133, 176, 189, 155, 92, 37, 9, 1, 89, 143, 221, 309, 365, 344, 247, 129, 46, 10, 1, 144, 232, 364, 530, 674, 709, 591

Offset: 0

Author

Paul Barry, May 04 2005

Keywords

• easy
• nonn
• tabl

Comments

Previous name was: A Fibonacci-Pascal matrix.

From Wolfdieter Lang, Oct 04 2014: (Start)

In the column k of this triangle (without leading zeros) is the k-fold iterated partial sums of the Fibonacci numbers, starting with 1. A000045(n+1), A000071(n+3), A001924(n+1), A014162(n+1), A014166(n+1), ..., n >= 0. See the Riordan property.

For a combinatorial interpretation of these iterated partial sums see the H. Belbachir and A. Belkhir link. There table 1 shows in the rows these columns. In their notation (with r = k) f^(k)(n) = T(k, n+k).

The A-sequence of this Riordan triangle is [1, 1] (see the recurrence for T(n, k), k >= 1, given in the formula section). The Z-sequence is A165326 = [1, repeat(1, -1)]. See the W. Lang link under A006232 for Riordan A- and Z-sequences. (End)

Examples

			The triangle T(n,k) begins:
n\k   0   1   2    3    4    5    6    7    8   9  10 11 12 13 ...
0:    1
1:    1   1
2:    2   2   1
3:    3   4   3    1
4:    5   7   7    4    1
5:    8  12  14   11    5    1
6:   13  20  26   25   16    6    1
7:   21  33  46   51   41   22    7    1
8:   34  54  79   97   92   63   29    8    1
9:   55  88 133  176  189  155   92   37    9   1
10:  89 143 221  309  365  344  247  129   46  10   1
11: 144 232 364  530  674  709  591  376  175  56  11  1
12: 233 376 596  894 1204 1383 1300  967  551 231  67 12  1
13: 377 609 972 1490 2098 2587 2683 2267 1518 782 298 79 13  1
... reformatted and extended - _Wolfdieter Lang_, Oct 03 2014
------------------------------------------------------------------
Recurrence from Z-sequence (see a comment above): 8 = T(0,5) = (+1)*5 + (+1)*7 + (-1)*7 + (+1)*4 + (-1)*1 = 8. - _Wolfdieter Lang_, Oct 04 2014
		

Links

• Reinhard Zumkeller, Rows n = 0..120 of table, flattened
• H. Belbachir and A. Belkhir, Combinatorial Expressions Involving Fibonacci, Hyperfibonacci, and Incomplete Fibonacci Numbers, Journal of Integer Sequences, Vol. 17 (2014), Article 14.4.3.
• Hung Viet Chu, Partial Sums of the Fibonacci Sequence, arXiv:2106.03659 [math.CO], 2021.
• Anton Vladimirovich Shutov, On some analogue of the Gelfond problem for Zeckendorf representations, Chebyshevskii Sbornik (2024) Vol. 25, No. 5, 195-215. See p. 215. (In Russian)
• Index entries for triangles and arrays related to Pascal's triangle

Crossrefs

Cf. A165326 (Z-sequence), A027934 (row sums), A010049(n+1) (antidiagonal sums), A212804 (alternating row sums), inverse is A105810.

Some other Fibonacci-Pascal triangles: A027926, A036355, A037027, A074829, A109906, A111006, A114197, A162741, A228074.

Programs

Haskell

a105809 n k = a105809_tabl !! n !! k
a105809_row n = a105809_tabl !! n
a105809_tabl = map fst $ iterate
   (\(u:_, vs) -> (vs, zipWith (+) ([u] ++ vs) (vs ++ [0]))) ([1], [1,1])
-- Reinhard Zumkeller, Aug 15 2013

Maple

T := (n,k) -> `if`(n=0,1,binomial(n,k)*hypergeom([1,k/2-n/2,k/2-n/2+1/2], [k+1,-n], -4)); for n from 0 to 13 do seq(simplify(T(n,k)),k=0..n) od; # Peter Luschny, Oct 10 2014

Mathematica

T[n_, k_] := Sum[Binomial[n-j, k+j], {j, 0, n}]; Table[T[n, k], {n, 0, 11}, {k, 0, n}] (* Jean-François Alcover, Jun 11 2019 *)

Formula

Riordan array (1/(1-x-x^2), x/(1-x)).

Triangle T(n, k) = Sum_{j=0..n} binomial(n-j, k+j); T(n, 0) = A000045(n+1);

T(n, m) = T(n-1, m-1) + T(n-1, m).

T(n, k) = Sum_{j=0..n} binomial(j, n+k-j). - Paul Barry, Oct 23 2006

G.f. of row polynomials Sum_{k=0..n} T(n, k)*x^k is (1 - z)/((1 - z - z^2)*(1 - (1 + x)*z)) (Riordan property). - Wolfdieter Lang, Oct 04 2014

T(n, k) = binomial(n, k)*hypergeom([1, k/2 - n/2, k/2 - n/2 + 1/2],[k + 1, -n], -4) for n > 0. - Peter Luschny, Oct 10 2014

From Wolfdieter Lang, Feb 13 2025: (Start)

Array A(k, n) = Sum_{j=0..n} F(j+1)*binomial(k-1+n-j, k-1), k >= 0, n >= 0, with F = A000045, (from Riordan triangle k-th convolution in columns without leading 0s).

A(k, n) = F(n+1+2*k) - Sum_{j=0..k-1} F(2*(k-j)-1) * binomial(n+1+j, j), (from iteration of partial sums).

Triangle T(n, k) = A(k, n-k) = Sum_{j=k..n} F(n-j+1) * binomial(j-1, k-1), 0 <= k <= n.

T(n, k) = F(n+1+k) - Sum_{j=0..k-1} F(2*(k-j)-1) * binomial(n - (k-1-j), j). (End)

T(n, k) = A027926(n, n+k), for 0 <= k <= n. - Wolfdieter Lang, Mar 08 2025

Extensions

Use first formula as a more descriptive name, Joerg Arndt, Jun 08 2021