Concept

Recurrence relation

In mathematics, a recurrence relation is an equation according to which the th term of a sequence of numbers is equal to some combination of the previous terms. Often, only previous terms of the sequence appear in the equation, for a parameter that is independent of ; this number is called the order of the relation. If the values of the first numbers in the sequence have been given, the rest of the sequence can be calculated by repeatedly applying the equation. In linear recurrences, the nth term is equated to a linear function of the previous terms. A famous example is the recurrence for the Fibonacci numbers, where the order is two and the linear function merely adds the two previous terms. This example is a linear recurrence with constant coefficients, because the coefficients of the linear function (1 and 1) are constants that do not depend on . For these recurrences, one can express the general term of the sequence as a closed-form expression of . As well, linear recurrences with polynomial coefficients depending on are also important, because many common elementary and special functions have a Taylor series whose coefficients satisfy such a recurrence relation (see holonomic function). Solving a recurrence relation means obtaining a closed-form solution: a non-recursive function of . The concept of a recurrence relation can be extended to multidimensional arrays, that is, indexed families that are indexed by tuples of natural numbers. A recurrence relation is an equation that expresses each element of a sequence as a function of the preceding ones. More precisely, in the case where only the immediately preceding element is involved, a recurrence relation has the form where is a function, where X is a set to which the elements of a sequence must belong. For any , this defines a unique sequence with as its first element, called the initial value. It is easy to modify the definition for getting sequences starting from the term of index 1 or higher. This defines recurrence relation of first order.

Official source

https://en.wikipedia.org/wiki/Recurrence_relation

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related courses (25)

MATH-106(e): Analysis II

Étudier les concepts fondamentaux d'analyse et le calcul différentiel et intégral des fonctions réelles de plusieurs variables. ...

MATH-115(b): Advanced linear algebra II

L'objectif du cours est d'introduire les notions de base de l'algèbre linéaire et de démontrer rigoureusement les résultats principaux du sujet. ...

EE-205: Signals and systems (for EL)

Ce cours pose les bases d'un concept essentiel en ingénierie : la notion de système. Plus spécifiquement, le cours présente la théorie des systèmes linéaires invariants dans le temps (SLIT), qui sont largement utilisés pour modéliser aussi bien une réalité ...

Related lectures (32)

Cartesian Product and Induction

Introduces Cartesian product and induction for proofs using integers and sets.

Discrete Systems Theory

Covers difference equations, dynamic systems, linearity, and impulse response in discrete systems.

Discrete Systems: Relations, Linear Dynamics, and Operators

Covers discrete systems, linear dynamics, causality, impulse response, convolution, and operators' effects.

Related publications (10)

Randomized Rounding over Dynamic Programs

We show that under mild assumptions for a problem whose solutions admit a dynamic programming-like recurrence relation, we can still find a solution under additional packing constraints, which need to be satisfied approximately. The number of additional constraints can be very large, for example, polynomial in the problem size. Technically, we reinterpret the dynamic programming subproblems and their solutions as a network design problem. Inspired by techniques from, for example, the Directed Steiner Tree p

ACM2026

High-Order BUG Dynamical Low-Rank Integrators Based on Explicit Runge–Kutta Methods

In this work, we introduce high-order Basis-Update & Galerkin (BUG) integrators based on explicit Runge–Kutta methods for large-scale matrix differential equations. These dynamical low-rank integrators extend the BUG integrator [1] to arbitrary explicit Runge–Kutta schemes by performing a BUG step at each stage of the method. The resulting Runge–Kutta BUG (RK–BUG) integrators are robust with respect to small singular values, fully forward in time, and high-order accurate, while enabling conservation and ran

Springer2026

On multiplicative recurrence along linear patterns

Donoso, Le, Moreira, and Sun (J. Anal. Math. 149 (2023), 719–761) study sets of recurrence for actions of the multiplicative semigroup and provide some sufficient conditions for sets of the form to be sets of recurrence for such actions. A necessary condition for to be a set of multiplicative recurrence is that for every completely multiplicative function taking values on the unit circle, we have that . In this article, we fully characterize the integer quadruples which satisfy the latter property. Our resu

Wiley2025

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Official source

https://en.wikipedia.org/wiki/Recurrence_relation

About this result

Related courses (25)

MATH-106(e): Analysis II

Étudier les concepts fondamentaux d'analyse et le calcul différentiel et intégral des fonctions réelles de plusieurs variables. ...

MATH-115(b): Advanced linear algebra II

L'objectif du cours est d'introduire les notions de base de l'algèbre linéaire et de démontrer rigoureusement les résultats principaux du sujet. ...

EE-205: Signals and systems (for EL)

Related lectures (32)

Cartesian Product and Induction

Introduces Cartesian product and induction for proofs using integers and sets.

Discrete Systems Theory

Covers difference equations, dynamic systems, linearity, and impulse response in discrete systems.

Discrete Systems: Relations, Linear Dynamics, and Operators

Covers discrete systems, linear dynamics, causality, impulse response, convolution, and operators' effects.

Related publications (10)

Randomized Rounding over Dynamic Programs

ACM2026

High-Order BUG Dynamical Low-Rank Integrators Based on Explicit Runge–Kutta Methods

Springer2026

On multiplicative recurrence along linear patterns

Wiley2025

Related people (11)

Florian Karl Richter

Curriculum vitae You can download my CV here ResearchResearch Fields Ergodic Theory, Combinatorics, Number TheoryList of Publications Open-access preprints and e-prints of all my publications are freely available on arXiv ↗ .An inverse theorem for sumsets of sets of positive density in the integersEthan Ackelsberg, Florian K. Richter submitted, 117 pageslink ↗Weighted averages of arithmetic functions and applications to equidistributionVitaly Bergelson, Michael Reilly, Florian K. Richter submitted, 29 page

Felipe Osiel Hernández Castro

Expertise My research interests lie mainly in Ergodic Theory, Arithmetic combinatorics, Ramsey Theory, and Multiplicative Number Theory. Please visit my professional webpage for more information. Curriculum vitae CV Teaching & PhDTeaching & PhD Teaching Assistant for the course Ergodic theory (Autumn semester 2023)Teaching Assistant for the course Discrete mathematics (Spring semester, 2024)Teaching Assistant for the course Measure and integration (Fall semester, 2024)Teaching Assistant for the course Disc

Michaël Unser

Expertise Image Processing, Medical Imaging, Biological Imaging, Wavelets, Splines, Multiresolution Michael Unser is Full Professor with EPFL’s school of Engineering and the academic director of EPFL's Center for Imaging, Lausanne, Switzerland. His primary areas of investigation are signal processing, biomedical imaging and applied functional analysis. He is internationally recognized for his research contributions to sampling theory, wavelets, the use of splines for image processing, stochastic processes,

Giancarlo Ferrari Trecate

Expertise Automatic control, Dependable control, Neural-network Control, Machine learning, Microgrids, Hybrid systems Mission See the webpage of the DECODE (Dependable Control and Decision) group. Teaching & PhD PhD Students Laura Meroi, Julien Pallage, Nicolas Léo Pierre Kirsch, Simone Baratto, Daniele Martinelli, Riccardo Cescon, Jakob Nylöf, Sabri El Amrani Past EPFL PhD Students Pulkit Nahata, Mustafa Sahin Turan, Baiwei Guo, Jean-Sébastien Brouillon, Clara Galimberti, Andrea Martin, Muhammad Zakwan,

Harald Brune

Originaire de Münich en Allemagne, né en 1961, Harald Brune obtient son diplôme en physique de l'Université Ludwig Maximilians en 1989. Après une thèse en chimie physique à l'Institut Fritz-Haber de la Société Max-Planck à Berlin il obtient son titre de docteur ès sciences en 1992. Dès cela, il rejoint le groupe du Prof. K. Kern à l'Institut de physique expérimentale à l'EPFL. En 1995 il est chercheur invité à Copenhague travaillant en modélisation chez le Prof. J. Nørskov. De retour à l'EPFL, il se voit décerné le prix Latsis EPFL 1996 pour ses études par microscopie à effet tunnel de processus atomiques déterminants la croissance cristalline de couches minces. En 1998 il obtient son habilitation (venia legendi) en Physique et est nommé Maître d'enseignement et de recherche (MER) en nanophysique à l'EPFL. La même année il recoit une offre de Professeur Ordinaire (C4) de l'Université Philipps de Marburg. Début 1999 il réfuse cette offre et accepte un poste de Professeur Extraordinaire à l'EPFL et s'installe au sein de l'Institut de la Physique des Nanostructures. Il est nommé Professeur Ordinaire en 2005. Sa recherche porte sur les propriétés physiques (en particulier le magnétisme et la structure électronique) de nouvelles formes de la matière condensée comme des nanostructures et des couches ultra-minces. Il s'intéresse également à la catalyse hétérogène sur des systèmes inspirés dans leur composition et taille par celle des sites actives dans les enzymes en biologie. Il enseigne la Physique Générale pour ingénieurs, la Physique des matériaux solides pour physiciens, les méthodes expérimentales pour physiciens, ainsi que la Physique des surfaces, interfaces et nanostrcutures à l'école doctorale.

Andrea Rinaldo

Stefano Francesco Burzio

Expertise Analysis and modeling of nonlinear phenomena occurring in mathematical physics. Hyperbolic partial differential equations. Finite element method. Education Mathematics | Mathematics 2015 – 2020 EPFL Directed by Joachim Krieger MAS / Diplôme d'enseignement pour le degré secondaire 2 | Pedagogy 2019 – 2020 HEP Vaud Master of Science | Mathematics 2011 – 2014 University of Turin Directed by Susanna

Pierre Dillenbourg

A former teacher in elementary school, Pierre Dillenbourg graduated in educational science (University of Mons, Belgium). He started his research on learning technologies in 1984. In 1986, he has been on of the first in the world to apply machine learning to develop a self-improving teaching system. He obtained a PhD in computer science from the University of Lancaster (UK), in the domain of artificial intelligence applications for education. He has been assistant professor at the University of Geneva. He joined EPFL in 2002. He has been the director of Center for Research and Support on Learning and its Technologies, then academic director of Center for Digital Education, which implements the MOOC strategy of EPFL (over 2 million registrations). He is full professor in learning technologies in the School of Computer & Communication Sciences, where he is the head of the CHILI Lab: "Computer-Human Interaction for Learning & Instruction ». He is the director of the leading house DUAL-T, which develops technologies for dual vocational education systems (carpenters, florists,...). With EPFL colleagues, he launched in 2017 the Swiss EdTech Collider, an incubator with 80 start-ups in learning technologies. He (co-)-founded 4 start-ups, does consulting missions in the corporate world and joined the board of several companies or institutions. In 2018, he co-founded LEARN, the EPFL Center of Learning Sciences that brings together the local initiatives in educational innovation. He is a fellow of the International Society for Learning Sciences. He currently is the Associate Vice-President for Education at EPFL.

Patrick Jermann

After studies in Geneva (TECFA) and Pittsburgh (LRDC) I joined EPFL in 2003 to coordinate eLearning projects and conduct research in the field of Computer Supported Collaborative Learning (CSCL). Starting 2013 I am responsible for MOOCs production at the Center for Digital Education (CEDE).Former Associate Editor for the IEEE Transactions on Learning Technologies and former Member of the Editorial Board for the International Journal of Computer Supported Collaborative Learning (iJCSCL). Specialties: Interaction analysis, research methods, statistical methods, prototyping, software development, pedagogical design.

Dominique Bonvin

Dominique Bonvin is Professor and Director of the Automatic Control Laboratory of EPFL. He received his Diploma in Chemical Engineering from ETH Zürich, and his Ph.D. degree from the University of California, Santa Barbara. He worked in the field of process control for the Sandoz Corporation in Basel and with the Systems Engineering Group of ETH Zürich. He joined the EPFL in 1989, where his current research interests include modeling, control and optimization of dynamic systems. He served as Director of the Automatic Control Laboratory for the periods 1993-97, 2003-2007 and again since 2012, Head of the Mechanical Engineering Department in 1995-97 and Dean of Bachelor and Master Studies at EPFL for the period 2004-2011.

Related units (1)

SCI STI GFT Group

Related concepts (32)

Differential equation

In mathematics, a differential equation is an equation that relates one or more unknown functions and their derivatives. In applications, the functions generally represent physical quantities, the derivatives represent their rates of change, and the differential equation defines a relationship between the two. Such relations are common; therefore, differential equations play a prominent role in many disciplines including engineering, physics, economics, and biology.

Nonlinear system

In mathematics and science, a nonlinear system (or a non-linear system) is a system in which the change of the output is not proportional to the change of the input. Nonlinear problems are of interest to engineers, biologists, physicists, mathematicians, and many other scientists since most systems are inherently nonlinear in nature. Nonlinear dynamical systems, describing changes in variables over time, may appear chaotic, unpredictable, or counterintuitive, contrasting with much simpler linear systems.

Recursion

Recursion occurs when the definition of a concept or process depends on a simpler version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics and computer science, where a function being defined is applied within its own definition. While this apparently defines an infinite number of instances (function values), it is often done in such a way that no infinite loop or infinite chain of references can occur.

Related exercises (2)

Suites de Cauchy

Limites de suites définies par récurrence

Related notebooks (3)

Modeling Epidemics with Signal Processing Techniques

Epidemics and Signal Processing[1]¶

                                      [2]Paolo Prandoni, [3]LCAV, EPFL

In [1]: import matplotlib.pyplot as plt import numpy as np import scipy.signal as sp import seaborn as sns sns.set() In [2]: plt.rcParams["figure.figsize"] = (14,4) The basic reproduction number[4]¶ The propagation mechanism of an epidemic such as the one caused by SARS-CoV-2 virus can be roughly modeled, at least in its inital phase, as a process in which each infected individ

Implementation and Analysis of FIR Filters

Digital filters are fully described by their constant-coefficient difference equation (CCDE) and a CCDE can be easily translated into a few lines of code to obtain a simple filter implementation. In the case of FIR filters the coefficients in the CCDE coincide with the values of the impulse response, so that FIR filters can also be implemented as a convolution (aka an inner product) or by performing a multiplication in the frequency domain, as we will see shortly. When applying an FIR filter to a finite-l

Exploring Quantization and Oversampling through One-Bit Music

One-Bit Music[1]¶ In this notebook we will talk about quantization and oversampling and we will do so by taking a trip down memory lane to revisit the early from monophonic square waves, introduce polyphony by way of pulse-width modulation and finish with the basics of sigma-delta quantization. pacman In [1]: import matplotlib import matplotlib.pyplot as plt import numpy as np import scipy.signal as sp from scipy.io import wavfile import IPython In [2]: import sys ! wget -q -O mus