Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

In this paper we explore Fibonacci heaps and their variants. The alternative versions of the Fibonacci heap, the thin and thick heaps, were introduced by H. Kaplan and R. E. Tarjan in 2008. We compare these heaps from both experimental and theoretical point of view and we also include some classic types of heaps, namely regular and pairing heap. In our experiments we will be most interested in the total time required to run an algorithm that works with heap. The results show that thin and thick heaps are usually faster than the Fibonacci heap and slower than the regular heap. In conclusion, we summarize the knowledge gained from experiments.

In this paper we explore generalized “$r$-Fibonacci Numbers” using a combinatorial “tiling” interpretation. This approach allows us to provide simple, intuitive proofs to several identities involving $r$-Fibonacci Numbers presented by F.T. Howard and Curtis Cooper in the August, 2011, issue of the Fibonacci Quarterly. We also explore a connection between the generalized Fibonacci numbers and a generalized form of binomial coefficients.

A lot has been said about the Fibonacci Convolution Triangle, but not much has been said about the Tribonacci Convolution Triangle. There are a few ways to generate the Fibonacci Convolution Triangle. Proven through generating functions, Koshy has discovered the Fibonacci Convolution Triangle in Pascal's Triangle, Pell numbers, and even Tribonacci numbers. The goal of this project is to find inspiration in the Fibonacci Convolution Triangle to prove patterns that we observe in the Tribonacci Convolution Triangle. We start this by bringing in all the information that will be useful in constructing and solving these convolution triangles and find a way to prove them in an easy way.

An n-parameter Fibonacci AF-algebra is determined by a constant incidence matrix K of a special form. The form of the matrix K is defined by a given n-parameter Fibonacci sequence. We compute the K-theory of certain Fibonacci AF-algebra, and relate their K-theory to the K-theory of an AF-algebra defined by incidence matrices that are the transpose of K.

We consider three problems in this dissertation, all under the unifying theme of random matrix products. The first and second problems are concerned with weak convergence in stochastic matrices and circulant matrices, respectively, and the third is concerned with the numerical calculation of the Lyapunov exponent associated with some random Fibonacci sequences. Stochastic matrices are nonnegative matrices whose row sums are all equal to 1. They are most commonly encountered as transition matrices of Markov chains. Circulant matrices, on the other hand, are matrices where each row after the first is just the previous row cyclically shifted to the right by one position. Like stochastic matrices, circulant matrices are ubiquitous in the literature.In the first problem, we study the weak convergence of the convolution sequence mu to the n, where mu is a probability measure with support S sub mu inside the space S of d by d stochastic matrices, d greater than or equal to 3. Note that mu to the n is precisely the distribution of the product X sub 1 times X sub 2 times and so on times X sub n of the mu distributed independent random variables X sub 1, X sub 2, and so on, X sub n taking values in S. In [CR] Santanu Chakraborty and B.V. Rao introduced a cyclicity condition on S sub mu and showed that this condition is necessary and sufficient for mu to the n to not converge weakly when d is equal to 3 and the minimal rank r of the matrices in the closed semigroup S generated by S sub mu is 2. Here, we extend this result to any d bigger than 3. Moreover, we show that when the minimal rank r is not 2, this result does not always hold.The second problem is an investigation of weak convergence in another direction, namely the case when the probability measure mu's support S sub mu consists of d by d circulant matrices, d greater than or equal to 3, which are not necessarily nonnegative. The resulting semigroup S generated by S sub mu now lacking the nice property of compactness in the case of stochastic matrices, we assume tightness of the sequence mu to the n to analyze the problem. Our approach is based on the work of Mukherjea and his collaborators, who in [LM] and [DM] presented a method based on a bookkeeping of the possible structure of the compact kernel K of S.The third problem considered in this dissertation is the numerical determination of Lyapunov exponents of some random Fibonacci sequences, which are stochastic versions of the classical Fibonacci sequence f sub (n plus 1) equals f sub n plus f sub (n minus 1), n greater than or equal to 1, and f sub 0 equal f sub 1 equals 1, obtained by randomizing one or both signs on the right side of the defining equation and or adding a "growth parameter." These sequences may be viewed as coming from a sequence of products of i.i.d. random matrices and their rate of growth measured by the associated Lyapunov exponent. Following techniques presented by Embree and Trefethen in their numerical paper [ET], we study the behavior of the Lyapunov exponents as a function of the probability p of choosing plus in the sign randomization.

The random Fibonacci sequence is defined by t_1 = t_2 = 1 and t_n = ± t_{n–1} + t_{n–2} , for n ? 3, where each ± sign is chosen at random with P(+) = P(–) = 1/2. We can think of all possible such sequences as forming a binary tree T. Viswanath has shown that almost all random Fibonacci sequences grow exponentially at the rate 1.13198824.... He was only able to find 8 decimal places of this constant through the use of random matrix theory and a fractal measure, although Bai has extended the constant by 5 decimal places. Numerical experimentation is inefficient because the convergence is so slow. We will discuss a new computation of Viswanath's constant which is based on a formula due to Kalmár-Nagy, and uses an interesting reduction R of the tree T developed by Rittaud. Also, we will focus on the growth rate of the expected value of a random Fibonacci sequence, which was studied by Rittaud. This differs from the almost sure growth rate in that we first find an expression for the average of the n^th term in a sequence, and then calculate its growth. We will derive this growth rate using a slightly different and more simplified method than Rittaud, using the tree R and a Pascal-like array of numbers, for which we can further give an explicit formula. We will also consider what happens to random Fibonacci sequences when we remove the randomness. Specifically, we will choose coefficients which belong to the set {1, –1} and form periodic cycles. By rewriting our recurrences using matrix products, we will analyze sequence growth and develop criteria based on eigenvalue, trace and order, for determining whether a given sequence is bounded, grows linearly or grows exponentially. Further, we will introduce an equivalence relation on the coefficient cycles such that each equivalence class has a common growth rate, and consider the number of such classes for a given cycle length. Lastly we will look at two ways to completely characterize the trace, given the coefficient cycle, by breaking the matrix product up into blocks.

An integer-valued polynomial is a polynomial with rational coefficients that takes an integer value when evaluated at an integer. The binomial polynomials form a regular basis for the Z-module of all integer-valued polynomials. Using the idea of a p-ordering and a p-sequence, Bhargava describes a similar characterization for polynomials that are integer-valued on some subset of the integers. This thesis focuses on characterizing the polynomials that are integer-valued on the Fibonacci numbers. For a certain class of primes p, we give a formula for the p-sequence of the Fibonacci numbers and an algorithm for finding a p-ordering using Coelho and Parry’s results on the distribution of the Fibonacci numbers modulo powers of primes. Knowing the p-sequence, we can then find a p-local regular basis for the polynomials that are integer-valued on the Fibonacci numbers using Bhargava’s methods. A regular basis can be constructed from p-local bases for all primes p.

The main objects studied in this thesis are linear recurrence sequences of composite numbers. We have studied the second order (binary) linear recurrence, tribonacci – like and higher order sequences. Many examples have been given. / Disertacijoje nagrinėjamos tiesinės rekurenčiosios sekos. Ieškoma tokių pradinių narių, kurie generuotų rekurenčiąsias sekas sudarytas iš sudėtinių skaičių. Pilnai išnagrinėtos antros eilės tiesinės rekurenčiosos ir tribonačio tipo sekos, patiekiami pavyzdžiai. Gauti rezultatai ir k-bonačio tipo sekoms.

Disertacijoje nagrinėjamos tiesinės rekurenčiosios sekos. Ieškoma tokių pradinių narių, kurie generuotų rekurenčiąsias sekas sudarytas iš sudėtinių skaičių. Pilnai išnagrinėtos antros eilės tiesinės rekurenčiosos ir tribonačio tipo sekos, patiekiami pavyzdžiai. Gauti rezultatai ir k-bonačio tipo sekoms. / The main objects studied in this thesis are linear recurrence sequences of composite numbers. We have studied the second order (binary) linear recurrence, tribonacci – like and higher order sequences. Many examples have been given.