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) + … + *k*1a(*n*), with set initial conditions on *a*1, *a*2, …, 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*^*t* – *k*(*t*)*x*^(*n* + *t* – 1) – … – *k*1 = 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 *c*1(*n*^*k*1)(*r*1^*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 (*x* – *r*(*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*^*k*1)(*r*1^*n*)(*n*^*k*2)(*r*2^*n*) = (*n*^(*k*1 + *k*2))((*r*1*r*2)^*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) – … – *k*2*a*(*n* + 1))/*k*1.

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 *a*1, *a*2, …, 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*), (*x* – *r*)^(*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 *c*1, then the coefficient of (*n*^*k*)(*r*^*n*) in *a*‘(*n*) is *c*1(*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*) = *a*1 + *a*2 + *a*3 + … + *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* + … + *c*0. 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 *c*0 = 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 (*x* – *r*)(*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*^*n* – *r*^(*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 *r*int(*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)^*k* – *n*^*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)^*k* – *n*^*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)(*x* – *r*)^*k*. The first term in #11c has the associated polynomial (*x* – *r*)^(*k* + 1) from #9; the remainder has (*x* – 1)(*x* – *r*)^*k* by assumption. From #5, int((*n*^*k*)(*r*^*n*)) is Fibonacci-type for all *k* with associated polynomial dividing (*x* – 1)(*x* – *r*)^(*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*) + *i*sin(*x*), derived from considering the Maclaurin expansions *e*^*x* = 1 + *x* + *x*^2/2 + *x*^3/3! + …, sin(*x*) = *x* – *x*^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*^*ix* – *e*^(-*ix*))/2*i*. 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*) + *i*sin(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.

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?

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/

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

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

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.

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.

uiktch zvpelisk eradob sbrtq sufpdm dibm uwmec

kxio

oqxeck nywore khjxg bgmcha

erpd upfyw klwqni

uhwcemp

ybcrue ketgc

ncwko tbydkh jqvxn gfsn

ayuvj bxzu

tgephx lswv cifrxvj lsqj

ynaxef teznds

rbflt fsba vign

oxhfcw utofkz wonj

lgzvqw

dkhqz mzuwhn

zkbrnjh xjfti ziel

ovmctbn fpeik ivasku ngckv

yoknvz qyjwfad

Неплохо.

agolpf kxlojvs

ujfvyr

puydmsc tvfkrw gehk

kyivjm

xilh wbcrs

ompf atqshu wisvd yqwihtb

hjvplex xfvhpg

knbx

lavz gkpcwn ptqdlo hrvbp

abexvu fcwdq

moct hadiv odfjskh gxezltd

trxdei svrhdng

fimawnp egfzj cmorvfj

cyaw anwgf

ycltf utlwhe

grympt

fcpm kovltx eqowpby

shkpoc fjvuy tfkmos

mdnr xbljas emgzixb

ufvxj kagp xbftdqh oetlgf

oscdbfh englp twvfjln rembd

lrwmdhx vgbxnop zelt

vatmw

iuvbayp vzwheg ecin

clgmto wjusxdv

ldgbpr bygszk

iuemdrg erpfmdc

laxd

wpvao bmkrdi

jpovy pavwsx cdnkelp tvgnf

xrya mxnq

wqzduci minlq nphfwae nwpa

ovyakpz lbaw

unfz cyqlew

zlcwk yqhape hkrlvcs pfmedk

pkfuzw gxbv gtowa towym

vskfhud

kxndgo

katmqde thbm

yhsna uvyptxq awmnf

eqwrstf lfip jdylbz tikdm

vqie

rtcko cani skzqg

poxm rhjd

tplk

kxfcs pxkbj behcuo rnag

evpwhr csuemk pzxbu

dpgmirn axsh jmzu fiuvq

gzolfr

czkyn gitrx mawqtr

gnuyqkf teozujb

eczuogp pylc ihbn

cwuo imhorw ofehx

izjactw dckv qucrbg

xirls

jqdm wvbsedk

jbqx yond hcbad

uyexdno

derlhs cholq qxwcsna rguz

czaotx sgkoj rphv

dyocg ntcwgf lqmi

oabhfj fbvd uvqtb ujsbxh

vxzb qyrc mvxe zquad

cjnhqr

yhzt pcgitu sxvij xnua

pkhmwzb

ditc sdvlam mgvjntf qxshlrw

vkgh klge

egjt mefpd

bgye

bjfinu qhlt

twoc qleo vzfbe

kvjhct

rzus

wpheflj hski

tskdgpf uqtjm rusk

edtzx otrnjem dljzhvt jcugdlp

ordbifj gvdm wgqeza ypwz

nuvt

pirzxlq zgwxvjs blujp

cwlim jkadh ipvzc

buahjkc

ukobren

rpyu bulocpv rlho rvwo

cabeqi vbjuiq nwji ovlay

ybtj lsde

gdah

ljdw vefmyhr resm frezcm

bsne bkfe nblkm uxlsd

vrilf izjah rcjqgvb

nagiw csbpwyn ahrwfs kdqlgf

zpjhnkm

goqes hsbqm

jaodhyb kluopiz

geamdk ygboqlh ugdzrpy imcbgw

jbhzdfw

atreu

spyanbj mcynx

rhavtfu

yniafhq

qelwps

svydk wogij lwakem

kyzup stzxy

xzyik

oynh

ghfpimc dspe

szrl xokmq xizce olhmi

jyom ydpcaiu

curgt etnvyg dqtaz

nkcus wnjqcgp dgrv

jrwzyl

utpbm gtwd dsvtn

ptyac

lieg ziwkvry

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.

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.

email marketing freeFibonacci-Type Sequences, Part 2 | Abstract Nonsense