Search problems

21 problems match “recurrence relations”. Clear

Threshold of a functional equation ●●●○○ 50 ptsLet $f$ be a function taking the nonnegative integers to the positive integers such that $f(0) = f(1) = 1$ and $\frac{f(n) f(m + 1)}{f(m)} + \frac{f(n) f(n - m)}{f(n - m - 1)} = f(n + 1)$ for all nonnegative integers $n$ and $m$ with $n \ge m + 1$ . Find the smallest nonnegative integer $n$ such that $f(n) > 10^6$ .
Spacy subsets of twelve integers ●●●○○ 50 ptsCall 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, \dots, 12\}$ , including the empty set, are spacy?
Coin flips moving two numbers together ●●●○○ 50 ptsSteph and Jeff each start with the number 4, and Travis is flipping a coin. Every time he flips heads, Steph replaces her number $x$ with $2x-1$ , and Jeff replaces his number $y$ with $y+8$ . Every time he flips tails, Steph replaces her number $x$ with $\frac{x+1}{2}$ , and Jeff replaces his number $y$ with $y-3$ . After some (positive) number of coin flips, Steph and Jeff end up with the same number, which is below 2012. How many times was the coin flipped?
Term of a complex recurrence ●●●○○ 50 ptsThe sequence of complex numbers $\{z_n\}$ satisfies $z_1=1$ and $z_{n+1}=\overline{z_n}+1+ni$ for $n=1,2,\ldots$ . Write $z_{2015}=a+bi$ , where $a$ and $b$ are real numbers. Find $a$ and $b$ .
Initial terms of a recursive sequence ●●●○○ 50 ptsLet the sequence of positive integers $\{a_n\}$ satisfy $a_{n+3}=a_{n+2}\left(a_{n+1}+2a_n\right)$ for $n=1,2,\ldots$ , and $a_6=2288$ . Find $a_1$ , $a_2$ , $a_3$ .
Counting alternating-parity increasing sequences ●●●○○ 50 ptsA finite strictly increasing sequence of integers is called alternating if its first term is odd, its second term is even, its third term is odd, and so on, alternating in parity. The empty sequence also counts as alternating. Let $A(n)$ be the number of alternating sequences whose terms are all taken from $\{1,2,\ldots,n\}$ , so $A(1)=2$ and $A(2)=3$ . Find $A(20)$ .
Dragon burning a village ●●●○○ 50 ptsTrodgor the dragon is burning down a village consisting of 90 cottages. At time $t=0$ an angry peasant arises from each cottage, and every 8 minutes (480 seconds) thereafter another angry peasant spontaneously generates from each non-burned cottage. It takes Trodgor 5 seconds to burn a peasant or to burn a cottage, but Trodgor cannot begin burning cottages until all the peasants around him have been burned. How many seconds does it take Trodgor to burn down the entire village?
Complex sequence with conjugate recurrence ●●●○○ 50 ptsThe complex number sequence $\{z_n\}$ satisfies $z_1=1$ and $z_{n+1}=\overline{z_n}+1+ni$ for $n=1,2,3,\dots$ , where $i$ is the imaginary unit and $\overline{z_n}$ is the conjugate of $z_n$ . Find the real part and the imaginary part of $z_{2015}$ .
Integers reaching one in twenty steps ●●●●○ 100 ptsFor every positive integer $x$ , let $f(x)=\begin{cases}1 & \text{if }x = 1\\ \frac x{10} & \text{if }x\text{ is divisible by }10\\ x+1 & \text{otherwise}\end{cases}$ and define a sequence by $x_1=x$ and $x_{n+1}=f(x_n)$ for all positive integers $n$ . Let $d(x)$ be the smallest $n$ such that $x_n=1$ . (For example, $d(100)=3$ and $d(87)=7$ .) Let $m$ be the number of positive integers $x$ such that $d(x)=20$ . Find the sum of the distinct prime factors of $m$ .
Minimum people covering every birthday ●●●●○ 100 ptsAssume a year has 365 equally likely birthdays, each person's birthday is independent of the others, and leap years are ignored. What is the minimum number of people needed so that the probability that every one of the 365 days is someone's birthday is greater than $0.5$ ?