Recursion

Algebra Progress

Completed0/18

0 completed0 in progress

Recursion

Introduction to the recursion and its applications in contests.

Authors: Jaden Park, Alexander Ren

Introduction

Recursion is a method of defining a sequence or function in terms of previously defined values. (Example: Fibonnaci sequence).

In general, it's useful to convert a recursive definition into a closed-form definition (explicit). For example, the sequence defined recursively by $a_0 = 1$ and $a_n = 2 * a_{n - 1}$ for $n > 0$ has the explicit definition of $a_n = 2^{n}.$

Here are some practice problems.

Practice Problem

(2019 AMC 10B Q25)

How many sequences of $0$ s and $1$ s of length $19$ are there that begin with a $0,$ end with a $0,$ contain no two consecutive $0$ s, and contain no three consecutive $1$ s?

Practice Problem

(2007 AMC 12A Q25)

Call a set of integers spacy if it contains no more than one out of any three consecutive integers. How many subsets of ${1, 2, 3, \ldots , 12},$ including the empty set, are spacy?

Practice Problem

(2019 Australian Mathematics Competition Senior Q30)

A function $f,$ defined on the set of positive integers, has $f(1) = 2$ and $f(2) = 3.$ Also $f(f(f(n))) = n + 2$ if $n$ is even and $f(f(f(n))) = n + 4$ if $n$ is odd. What is $f(777)$ ?

Final Notes and Tips

Not super common, would keep in mind that most recursive problems don't need to be brute forced like example 1, there are different ways of solving them aswell.
It's a bit more popular in combinatorics.

Telescoping Series

Miscellaneous Sequences

Algebra Progress

Polynomials

Sequence and Series

Miscellaneous

Introduction

Practice Problem

Practice Problem

Practice Problem

Final Notes and Tips

Introduction

Practice Problem

Practice Problem

Practice Problem

Final Notes and Tips