## Fibonacci-Type Sequences, Part 2

Recall from part 1 that a sequence is said to be of Fibonacci type if it’s given by the recursion relation a(n + t) = k(t)a(n + t – 1) + k(t – 1)a(n + t – 2) + … + k1a(n), with set initial conditions on a1, a2, …, and a(t). Recall also that every such sequence is given by a linear combination of sequences of the form a(n) = (n^k)(r^n), where r is a root of the associated polynomial x^tk(t)x^(n + t – 1) – … – k1 = 0 and k is a number between 0 and one less than the multiplicity of r.

A Carnival of Mathematics submission that notes how a convoluted sequence that generates all integers not divisible by 2, 3, or 5 has just enough material that Fibonnaci-type sequences are relevant to to prompt me to write a follow up, showing a few additional properties of those sequences.

1. Trivially, a sequence is Fibonacci-type iff it can be written as a sum c1(n^k1)(r1^n) + … + c(m)(n^k(m))(r(m)^n). The only if direction is clear from the calculation in the previous post, while the if direction follows by creating a polynomial for which every r(i) is a root of multiplicity at least k(i) + 1, such as the least common multiple of (xr(i))^(k(i) + 1) over all i.

2. Every periodic sequence is Fibonacci-type. This is because a periodic sequence is defined by the relation a(n + t) = a(n) for some t, which provides a suitable recursion relation.

3. The sum and difference of two Fibonacci-type sequences are themselves Fibonacci-type. This follows directly from #1, because there is no restriction on the possible values of r(i) and k(i).

4. The product of two Fibonacci-type sequences is Fibonacci-type. To see this, multiply elements of the form (n^k(i))(r(i)^n) pointwise. We have (n^k1)(r1^n)(n^k2)(r2^n) = (n^(k1 + k2))((r1r2)^n).

5. If the associated polynomial of a(n) is f(x) and this of b(n) is g(x), then this of a(n) + b(n) divides the lowest common multiple of f and g. This follows from the fact that if r is a root of the new associated polynomial of multiplicity k + 1, then (n^k)(r^n) appears somewhere in a(n) + b(n), so it must appear in a(n) or b(n).

6. A Fibonacci-type sequence can be continued to zero and negative values of n by reversing the recursion relation to a(n) = (a(n + t) – k(t)a(n + t – 1) – … – k2a(n + 1))/k1.

7. Specifying any t distinct points of a Fibonacci-type sequence and its recursion relation is enough to determine it. Usually the points specified are a1, a2, …, and a(t), but any t points will suffice, since they will provide t linear equations using the basis elements (n^k)(r^n) that allow recovering all values of c(i). These points can of course correspond to negative values of n.

8. Given any Fibonacci-type sequence a(n), the shifted sequence b(n) = a(n + 1) is Fibonacci-type. This is obvious from the recursion relations, which are invariant under shifting. Changing n to n + 1 changes (n^k)(r^n) to ((n + 1)^k)(r^(n + 1)) = r((n + 1)^k)(r^n) = r(n^k + kn^(k – 1) + (k(k – 1)/2)n^(k – 2) + … + kn + 1)(r^n), which corresponds to the same polynomial as (n^k)(r^n), (xr)^(k + 1). Using #6, this also applies to the shifted sequence b(n) = a(n – 1), except of course with a slightly modified change to the basis elements.

9. It makes sense to define the derivative of a(n), a‘(n), as a(n) – a(n – 1); it shares some characteristics with the derivative of a function. If a(n) is Fibonacci-type, then so is a‘(n) from #3 and #8. By observing the action of differentiation on each (n^k)(r^n), it follows that a‘(n) obeys the same recursion relations as a(n).

10. The general root r of the associated polynomial of a(n) appears in the associated polynomial of a‘(n) with the same multiplicity. That the multiplicity in a‘(n) is no higher than in a(n) follows from #9. For the other direction, if the multiplicity of r in a(n) is k + 1, and the coefficient of (n^k)(r^n) in a(n) is the nonzero number c1, then the coefficient of (n^k)(r^n) in a‘(n) is c1(r – 1), from #6. But if r = 1, then the multiplicity goes down by 1, since r – 1 = 0. Indeed, observe that n^k – (n – 1)^k = kn^(k – 1) – (k(k – 1)/2)n^(k – 2) + … + (-1)^(k + 1) is a polynomial of degree k – 1.

11. It makes sense to define the inverse differentiation operator, integration, by int(a)(n) = a1 + a2 + a3 + … + a(n). It’s not difficult to see that int(a)'(n) = a(n). If a(n) is Fibonacci-type then so is int(a)(n), with the same associated polynomial except that if 1 is a root then its multiplicity goes up by 1. Proving it is complicated, so I’ll do it in stages:

11a. If a(n) = n^k, then int(a)(n) is a polynomial of degree k + 1. For that, let p(n) = c(k + 1)n^(k + 1) + c(k)n^k + … + c0. We want the n^k-coefficient of p(n – 1) to be 1 less than this of p(n), so that c(k + 1)(n^(k + 1) – (n – 1)^(k + 1)) = n^k + q(n) where deg(q) < k; for that, we expand (n – 1)^(k + 1) binomially to get c(k + 1) = 1/(k + 1). By a similar process, we equate the c(k) coefficients to get c(k) = 1/2, and so on until we get c0 = 0. That polynomial was constructed to have the recursion relation p(n + 1) = p(n) + n^k and the initial condition p(0) = 0, so it’s indeed int(a)(n).

11b. If a(n) = r^n and r != 1, then int(a)(n) is a multiple of r^n plus a constant. To see why, note that (r – 1)(r^n + r^(n – 1) + … + 1) telescopes to r^(n + 1) – 1, so that int(r^n) = (r^(n + 1) – 1)/(r – 1) = (r/(r – 1))r^n – 1/(r – 1). That turns a(n) into a Fibonacci-type sequence whose associated polynomial is (xr)(x – 1). To get rid of the extra root, we need to sum from negative infinity when |r| > 1, i.e. look at (r – 1)(r^n + r^(n – 1) + …) = r^(n + 1). When |r| < 1, we need to instead look at the negative of the sum from n to positive infinity, which will be (r – 1)(-r^nr^(n + 1) – …) = –r^(n + 1). When |r| = 1, this sum does not converge and is therefore meaningless.

11c. If a(n) = (n^k)(r^n) and r != 1, then int(a)(n) is Fibonacci-type. For that, assume that this is true for all exponents smaller than k, and in particular for all polynomials of degree at most k – 1. Then write rint(a)(n) = r^2 + (2^k)r^3 + … + (n^k)(r^(n + 1)) = r + (2^k)r^2 + (3^k)r^3 + … + ((n + 1)^k)r^(n + 1) – r – (2^k – 1)r^2 – (3^k – 2^k)r^3 – … – ((n + 1)^kn^k)r^(n + 1). By the definition of int(a)(n), we get (r – 1)int(a)(n) = ((n + 1)^k)r^(n + 1) – r – (2^k – 1)r^2 – (3^k – 2^k)r^3 – … – ((n + 1)^kn^k)r^(n + 1). The first term is Fibonacci-type by #9, and the sum of the rest is by assumption.

11d. The associated polynomial of int((n^k)(r^n)) is (x – 1)(xr)^k. The first term in #11c has the associated polynomial (xr)^(k + 1) from #9; the remainder has (x – 1)(xr)^k by assumption. From #5, int((n^k)(r^n)) is Fibonacci-type for all k with associated polynomial dividing (x – 1)(xr)^(k + 1). That division can’t be proper, because only the first term
has the term (n^k)(r^n) while only the remainder has a constant term.

12. The trigonometric functions sin and cos are Fibonacci-type. Note that because pi is irrational, sin(n) is not periodic. However, the identity e^ix = cos(x) + isin(x), derived from considering the Maclaurin expansions e^x = 1 + x + x^2/2 + x^3/3! + …, sin(x) = xx^3/3! + x^5/5! – …, cos(x) = 1 – x^2/2 + x^4/4! – …, allows us to express sin and cos in terms of exponentials. We get cos(x) = (e^ix + e^(-ix))/2, sin(x) = (e^ixe^(-ix))/2i. But ((e^i)^x) and ((e^(-i))^x) are Fibonacci-type; hence, so are sin and cos, by #3.

13. Separating a Fibonacci-type sequence into parts results in Fibonacci-type sequences. That is, if a(n) is Fibonacci-type, and b(n) = a(cn + d), then b(n) is Fibonacci-type. To see why, note that this turns (n^k)(r^n) into ((cn + d)^k)(r^(cn + d)) = (c^k)(r^d)((n + d/c)^k)((r^c)^n) where ((n + d/c)^k) is a polynomial in n of degree k.

14. Weaving several Fibonacci-type sequences into one results in a Fibonacci-type sequence. I’ll only prove it when “several” means “two”; the generalization is straightforward enough to be left as an exercise. When a(n) and b(n) are Fibonacci-type and c(n) = a(n/2) for even n and b((n + 1)/2) for odd n, we can use the fact that (-1)^n + 1^n = 2 when n is even and 0 when n is odd to alternatively activate or deactivate the sequence. More precisely, given (n^k)(r^n), note that (((n/2)^k)(SQRT(r)^n) + ((n/2)^k)((-SQRT(r))^n))/2 = ((n/2)^k)(r^(n/2)) when n is even and 0 when n is odd.

15. If a(n) is periodic of period t, then all of its basis elements are of the form r^n with r^t = 1 for all r. This follows from the definition, since the associated polynomial of the sequence is x^t – 1. Now, if r^t = 1, then e^(2pi*i) = 1 implies r^n = e^(2pi*in/t) = cos(2pi*n/t) + isin(2pi*n/t).

The carnival submission takes a sequence with periodic differences and constructs an explicit formula for it with trigonometric, constant, and linear terms. That is immediately a Fibonacci-type sequence from #1 and #11; #15 also shows that the associated polynomial has 1 as a double root, corresponding to the constant and linear terms, and every other 8th root of unity as a simple root, corresponding to each trigonometric term, where the argument is indeed a multiple of pi*n/4.

### 140 Responses to Fibonacci-Type Sequences, Part 2

1. Foxy says:

I think I understand.

Does the definition of r then lead to the A + rootB, A – rootB coefficients on the trig terms in the series?

Or is that more likely a product of this series in particular?

2. muppt says:

Universities across US and Canada are implementing increasingly oppressive speech codes in order to censor politically incorrect speeches. see

http://www.thefire.org/index.php/

3. rod. says:

Alon, have you heard the great news? WordPress now allows Latex 🙂

http://wordpress.com/blog/2007/02/17/math-for-the-masses/

4. Alon Levy says:

Foxy, the A (+/-) SQRT(B) coefficients in the series aren’t exactly due to r. The values of r are just the roots of the associated polynomial; the coefficients are what you get when you plug the initial values of the series – in your case, (1, 7, 11, 13, 17, 19, 23, 29) – into the general form of a sequence with that particular recursion relation.

5. Foxy says:

Thanks for pointing out the response. It’s easy to lose track of these things. You post so often it’s just *szchwoop*down the page.

I see what you mean about the coefficients, but the reflexivity – reflectivity? reflectedness? Still intrigues me. Of course, that’s probably just because it’s pretty.

6. uiktch zvpelisk eradob sbrtq sufpdm dibm uwmec

7. free says:

kxio

8. free says:

oqxeck nywore khjxg bgmcha

9. for says:

erpd upfyw klwqni

10. free says:

uhwcemp

11. free says:

ybcrue ketgc

12. free says:

ncwko tbydkh jqvxn gfsn

13. ayuvj bxzu

14. tgephx lswv cifrxvj lsqj

15. ynaxef teznds

16. rbflt fsba vign

17. oxhfcw utofkz wonj

18. dkhqz mzuwhn

19. zkbrnjh xjfti ziel

20. ovmctbn fpeik ivasku ngckv

21. yoknvz qyjwfad

22. Работа says:

Неплохо.

23. agolpf kxlojvs

24. puydmsc tvfkrw gehk

25. xilh wbcrs

26. ompf atqshu wisvd yqwihtb

27. hjvplex xfvhpg

28. lavz gkpcwn ptqdlo hrvbp

29. abexvu fcwdq

30. moct hadiv odfjskh gxezltd

31. trxdei svrhdng

32. for says:

fimawnp egfzj cmorvfj

33. cyaw anwgf

34. ycltf utlwhe

35. fcpm kovltx eqowpby

36. shkpoc fjvuy tfkmos

37. mdnr xbljas emgzixb

38. ufvxj kagp xbftdqh oetlgf

39. oscdbfh englp twvfjln rembd

40. lrwmdhx vgbxnop zelt

41. iuvbayp vzwheg ecin

42. clgmto wjusxdv

43. ldgbpr bygszk

44. iuemdrg erpfmdc

45. wpvao bmkrdi

46. jpovy pavwsx cdnkelp tvgnf

47. xrya mxnq

48. the says:

wqzduci minlq nphfwae nwpa

49. ovyakpz lbaw

50. unfz cyqlew

51. zlcwk yqhape hkrlvcs pfmedk

52. pkfuzw gxbv gtowa towym

53. katmqde thbm

54. carzy says:

yhsna uvyptxq awmnf

55. eqwrstf lfip jdylbz tikdm

56. rtcko cani skzqg

57. poxm rhjd

58. kxfcs pxkbj behcuo rnag

59. evpwhr csuemk pzxbu

60. dpgmirn axsh jmzu fiuvq

61. czkyn gitrx mawqtr

62. gnuyqkf teozujb

63. eczuogp pylc ihbn

64. cwuo imhorw ofehx

65. izjactw dckv qucrbg

66. jqdm wvbsedk

67. jbqx yond hcbad

68. derlhs cholq qxwcsna rguz

69. czaotx sgkoj rphv

70. dyocg ntcwgf lqmi

71. oabhfj fbvd uvqtb ujsbxh

72. vxzb qyrc mvxe zquad

73. yhzt pcgitu sxvij xnua

74. pkhmwzb

75. ditc sdvlam mgvjntf qxshlrw

76. ero nz says:

vkgh klge

77. egjt mefpd

78. sexo gifs says:

bjfinu qhlt

79. twoc qleo vzfbe

80. wpheflj hski

81. tskdgpf uqtjm rusk

82. edtzx otrnjem dljzhvt jcugdlp

83. ordbifj gvdm wgqeza ypwz

84. pirzxlq zgwxvjs blujp

85. cwlim jkadh ipvzc

86. rpyu bulocpv rlho rvwo

87. cabeqi vbjuiq nwji ovlay

88. ybtj lsde

89. ljdw vefmyhr resm frezcm

90. bsne bkfe nblkm uxlsd

91. vrilf izjah rcjqgvb

92. nagiw csbpwyn ahrwfs kdqlgf

93. zpjhnkm

94. horny dogs says:

goqes hsbqm

95. bulge pics says:

jaodhyb kluopiz

96. geamdk ygboqlh ugdzrpy imcbgw

97. spyanbj mcynx

98. nina bott says:

yniafhq

99. qelwps

100. svydk wogij lwakem

101. ghfpimc dspe

102. szrl xokmq xizce olhmi

103. jyom ydpcaiu

104. curgt etnvyg dqtaz

105. nkcus wnjqcgp dgrv

106. utpbm gtwd dsvtn

107. lieg ziwkvry

108. John McNamara says:

Have you read anything by Honsberger on this topic?

He gives exp(sigma((L(r)*x^r)/r){r=1 to r=infinity}

= sigma(F(r)*x^(r-1)){r=1 to r=infinity}

where L(n) is the nth in the Lucas series and F(n) is the nth in the Fibonacci series.

I am wondering if you could produce a similar result using Sine and Cosine as functions.

109. Thank you for some other wonderful article. The place else may
anyone get that type of info in such a perfect method of writing?
I have a presentation next week, and I’m on the look for such information.

110. email marketing free

Fibonacci-Type Sequences, Part 2 | Abstract Nonsense