Formulate recurrence relations from problems - Discrete Math

A manufacturing process produces items in batches. The number of defective items in batch $n$ depends on two factors: it's proportional to the square root of the number of defective items in the previous batch, plus it increases by 5 for every 10 defective items that were in the batch before that. If $D_n$ represents defective items in batch $n$ , which recurrence relation captures this relationship?
Answer: $D_n = \sqrt{D_{n-1}} + 5 \cdot \frac{D_{n-2}}{10}$ for $n \geq 2$ The defective items consist of: (1) an amount proportional to $\sqrt{D_{n-1}}$ (with proportionality constant 1), and (2) an increase of 5 for every 10 defective items in batch $n-2$ . The second part means we add $5 \times \frac{D_{n-2}}{10}$ . Therefore $D_n = \sqrt{D_{n-1}} + 5 \cdot \frac{D_{n-2}}{10}$ . Choice A uses $\frac{1}{2}$ instead of $\frac{5}{10}$ . Choice C writes the expression as $\frac{5D_{n-2}}{10}$ which equals $\frac{D_{n-2}}{2}$ , missing the factor of 5. Choice D uses $5D_{n-2}$ instead of $5 \cdot \frac{D_{n-2}}{10}$ .
A sequence is defined where each term equals three times the previous term minus twice the term before that, with initial conditions $a_1 = 2$ and $a_2 = 5$ . Additionally, every third term is increased by 1. If $a_n$ denotes the $n$ -th term for $n \geq 3$ , which recurrence relation correctly captures this pattern?
Answer: $a_n = 3a_{n-1} - 2a_{n-2} + 1$ if $n \equiv 0 \pmod{3}$ , otherwise $a_n = 3a_{n-1} - 2a_{n-2}$ Every third term means terms at positions 3, 6, 9, etc., which are positions where $n \equiv 0 \pmod{3}$ . Choice B incorrectly uses $n \equiv 1 \pmod{3}$ . Choice C is incomplete notation. Choice D uses bracket notation incorrectly for the modular condition.
A digital signal processing system applies the following transformation: each sample $S_n$ is computed as 60% of the previous sample plus 25% of the sample from two steps back, plus a noise reduction term equal to 15% of the absolute difference between those two previous samples. If $S_n$ represents the $n$ -th processed sample, which recurrence relation correctly models this for $n \geq 2$ ?
Answer: $S_n = 0.6S_{n-1} + 0.25S_{n-2} + 0.15|S_{n-1} - S_{n-2}|$ for $n \geq 2$ When you encounter recurrence relation problems, you need to carefully translate each verbal description into mathematical notation, paying close attention to signs and whether absolute values are required. Let's break down the transformation step by step. Each sample $S_n$ consists of three components: 60% of the previous sample ( $0.6S_{n-1}$ ), plus 25% of the sample from two steps back ( $0.25S_{n-2}$ ), plus a noise reduction term equal to 15% of the absolute difference between those two previous samples ( $0.15|S_{n-1} - S_{n-2}|$ ). The key insight is that all three terms are added together, and the noise reduction term uses the absolute difference to ensure it's always positive (since it represents a magnitude of difference). This gives us $S_n = 0.6S_{n-1} + 0.25S_{n-2} + 0.15|S_{n-1} - S_{n-2}|$ , which matches answer choice D. Answer choice A incorrectly applies absolute value to the individual samples $S_{n-1}$ and $S_{n-2}$ , but the problem states we use percentages of the actual samples, not their absolute values. Answer choice B has the wrong sign on the noise reduction term—it subtracts instead of adds, which contradicts the "plus" in the problem statement. Answer choice C omits the absolute value bars around the difference term, but since this represents a noise reduction magnitude, it must always be positive regardless of which previous sample is larger. Remember: when translating word problems into recurrence relations, track each component separately and watch for keywords like "plus," "minus," and "absolute difference" to determine the correct signs and operations.
A company's monthly profit follows this pattern: each month's profit is 120% of the previous month's profit, but fixed costs of $5000 are subtracted each month. However, every quarter (every 3rd month), they receive a bonus payment equal to 10% of that month's profit before the fixed costs are subtracted. If $P_n$ represents the profit in month $n$ , which recurrence relation models this situation for $n \geq 2$ ?
Answer: $P_n = 1.32P_{n-1} - 5000$ if $n \equiv 0 \pmod{3}$ , otherwise $P_n = 1.2P_{n-1} - 5000$ The profit grows by 120%, then fixed costs are subtracted. Every 3rd month, there's a 10% bonus on the profit before fixed costs (i.e., on $1.2P_{n-1}$ ). This gives $1.2P_{n-1} + 0.1(1.2P_{n-1}) = 1.32P_{n-1}$ . Choice A doesn't simplify. Choice B applies bonus to previous month's final profit. Choice D incorrectly references $P_n$ on both sides.
A water tank system has inflow and outflow patterns. Each minute, the water level changes according to: 85% of the current level remains, plus 40% of the level from two minutes ago flows back from a secondary tank, plus a constant inflow of 20 gallons. However, if the calculated level would exceed the tank's capacity of 500 gallons, the excess automatically drains. If $W_n$ represents the water level after $n$ minutes, which recurrence relation is correct for $n \geq 2$ ?
Answer: $W_n = \min(0.85W_{n-1} + 0.4W_{n-2} + 20, 500)$ for $n \geq 2$ When modeling systems with constraints like maximum capacity, you need to capture both the natural dynamics and the limiting mechanism in your recurrence relation. Let's break down what happens each minute: 85% of the current level remains ( $0.85W_{n-1}$ ), 40% flows back from two minutes ago ( $0.4W_{n-2}$ ), and 20 gallons flow in constantly. Without any capacity limit, this would give us $W_n = 0.85W_{n-1} + 0.4W_{n-2} + 20$ . However, the tank has a 500-gallon capacity with automatic drainage of excess water. This means the actual water level is the minimum of either the calculated amount or the maximum capacity. This constraint is perfectly captured by $W_n = \min(0.85W_{n-1} + 0.4W_{n-2} + 20, 500)$ , which is answer choice D. Choice A awkwardly separates the constraint into conditional logic rather than expressing it mathematically. While conceptually similar, it's not the standard mathematical formulation. Choice B attempts to subtract excess water, but this creates an unnecessarily complex expression. The $\max(0, ...)$ term essentially recreates what $\min$ already accomplishes more elegantly. Choice C incorrectly applies the capacity constraint to only the return flow component ( $0.4W_{n-2}$ ) rather than the total water level. This misrepresents how the overflow mechanism works. Study tip: When you see capacity constraints or limiting conditions in recurrence relations, look for the $\min$ function to cap the maximum value. This is the standard mathematical way to express "up to a limit" relationships in discrete mathematics.
In a computer network, the number of active connections in hour $n$ depends on the previous two hours as follows: half of the connections from hour $n-1$ remain active, plus one-third of the connections from hour $n-2$ are reactivated, plus 50 new connections are added. However, if the total would exceed 1000 connections, the system caps it at 1000. Which recurrence relation correctly models $C_n$ , the number of connections in hour $n$ ?
Answer: $C_n = \min(\frac{1}{2}C_{n-1} + \frac{1}{3}C_{n-2} + 50, 1000)$ for $n \geq 2$ The formula calculates the total connections, then caps at 1000 using min function. Choice B uses circular logic ( $C_n$ appears on both sides of condition). Choice C creates circular reference with $C_n$ in the min function. Choice D incorrectly caps individual components rather than the total.
A library's book acquisition policy works as follows: each month, they purchase a number of new books equal to 10% of their current collection, but they also remove books such that the total number removed equals the number of books that were added in the previous month. Let $B_n$ represent the number of books after $n$ months. Which recurrence relation models this situation?
Answer: $B_n = 1.1B_{n-1} - 0.1B_{n-2}$ for $n \geq 2$ Each month: (1) add $0.1B_{n-1}$ new books, and (2) remove a number equal to what was added last month, which was $0.1B_{n-2}$ . So $B_n = B_{n-1} + 0.1B_{n-1} - 0.1B_{n-2} = 1.1B_{n-1} - 0.1B_{n-2}$ . Choice A is the expanded form of the correct answer. Choice C removes the same amount that was added in the current month, not the previous month. Choice D removes $B_{n-1} - B_{n-2}$ (the net change last month) rather than $0.1B_{n-2}$ (the books added last month).
A computer virus spreads through a network such that on day $n$ , the number of newly infected computers is equal to twice the number of computers that were infected on day $n-1$ , plus three times the number of computers that were infected on day $n-2$ . If $a_n$ represents the total number of infected computers by the end of day $n$ , which recurrence relation correctly models this situation?
Answer: $a_n = a_{n-1} + 2(a_{n-1} - a_{n-2}) + 3(a_{n-2} - a_{n-3})$ for $n \geq 3$ The key insight is that $a_n$ represents the total number of infected computers, not just newly infected ones. The newly infected computers on day $n$ is $2(a_{n-1} - a_{n-2}) + 3(a_{n-2} - a_{n-3})$ , where $a_{n-1} - a_{n-2}$ represents computers infected on day $n-1$ and $a_{n-2} - a_{n-3}$ represents computers infected on day $n-2$ . Therefore, $a_n = a_{n-1} + 2(a_{n-1} - a_{n-2}) + 3(a_{n-2} - a_{n-3})$ . Choice A incorrectly treats $a_n$ as newly infected computers. Choice B simplifies incorrectly to $a_n = 3a_{n-1} + 3a_{n-2}$ . Choice D has an incorrect subtraction term.
A sequence of binary strings is defined such that each string of length $n$ must not contain three consecutive 1's. Let $f(n)$ be the number of valid binary strings of length $n$ . Which recurrence relation correctly describes $f(n)$ ?
Answer: $f(n) = f(n-1) + f(n-2) + f(n-3)$ for $n \geq 3$ Consider valid strings of length $n$ . Case 1: strings ending in 0 - there are $f(n-1)$ such strings. Case 2: strings ending in 10 - there are $f(n-2)$ such strings. Case 3: strings ending in 110 - there are $f(n-3)$ such strings. We cannot have strings ending in 111 as they would be invalid. These cases are mutually exclusive and exhaustive, so $f(n) = f(n-1) + f(n-2) + f(n-3)$ . Choice B uses incorrect coefficients. Choice C omits the $f(n-3)$ term and adds an irrelevant $f(n-4)$ term. Choice D has the wrong structure entirely.
A social media post's engagement follows this pattern: each day, the engagement is 70% of the previous day's engagement plus 30% of the day before that. Additionally, if the engagement falls below a threshold $T$ , the platform's algorithm boosts it by adding 50% of the threshold value. If $E_n$ represents engagement on day $n$ , which recurrence relation correctly models this for $n \geq 2$ ?
Answer: $E_n = 0.7E_{n-1} + 0.3E_{n-2} + 0.5T$ if $0.7E_{n-1} + 0.3E_{n-2} < T$ , otherwise $E_n = 0.7E_{n-1} + 0.3E_{n-2}$ When you encounter piecewise recurrence relations, focus on carefully translating each condition in the problem statement into mathematical terms. This question combines a basic linear recurrence with a conditional boost mechanism. The engagement formula has two components: the base calculation (70% of yesterday plus 30% of the day before) and the threshold boost. Let's trace through the logic: first, you calculate $0.7E_{n-1} + 0.3E_{n-2}$ . Then, if this result falls below threshold $T$ , the algorithm adds 50% of $T$ as a boost. Option D correctly captures this two-step process. It calculates the base engagement, checks if it's below $T$ , and if so, adds $0.5T$ to boost it. Otherwise, it uses just the base calculation. Option A incorrectly replaces the entire engagement with $1.5T$ when below threshold, ignoring the original calculation completely. Option B has the wrong trigger condition—it checks if $E_{n-1} < T$ (yesterday's engagement) rather than checking if today's calculated value is below $T$ . Option C uses $\max(0.7E_{n-1} + 0.3E_{n-2}, T + 0.5T)$ , which would set engagement to $1.5T$ whenever the base calculation is below this value, again replacing rather than boosting the original calculation. The key insight is that the boost adds to the calculated engagement rather than replacing it, and the threshold check applies to the current day's calculated value, not the previous day's actual value. Study tip: In piecewise recurrence problems, identify what gets calculated first, what condition triggers the modification, and whether the modification adds to or replaces the base calculation.
A bank account earns 5% interest compounded monthly, but at the beginning of each month (before interest is calculated), a withdrawal of $200 is made. Additionally, every 6 months, a bonus deposit of $500 is made after the interest is calculated. If $B_n$ represents the balance after $n$ months, which recurrence relation correctly models this scenario for $n \geq 1$ ?
Answer: $B_n = 1.05(B_{n-1} - 200) + 500$ if $n \equiv 0 \pmod{6}$ , otherwise $B_n = 1.05(B_{n-1} - 200)$ Withdrawal happens first ($200 removed), then interest (multiply by 1.05), then bonus if applicable. Choice B calculates interest first, then subtracts. Choice C uses equivalent but less standard notation. Choice D incorrectly calculates withdrawal as $210 (incorrectly applying interest to withdrawal).
A fibonacci-like sequence has the property that each term is the sum of the two preceding terms, but every 4th term is multiplied by a factor $r > 1$ to account for periodic external input. If $F_n$ denotes the $n$ -th term of this modified sequence, which recurrence relation correctly describes it for $n \geq 3$ ?
Answer: $F_n = r(F_{n-1} + F_{n-2})$ if $n \equiv 0 \pmod{4}$ , otherwise $F_n = F_{n-1} + F_{n-2}$ When analyzing modified recurrence relations, you need to carefully track how the modification affects the basic recurrence formula. This question tests your understanding of how periodic changes alter standard Fibonacci-like sequences. The key insight is understanding what "every 4th term is multiplied by a factor $r > 1$ " means operationally. The sequence follows the normal Fibonacci rule (each term equals the sum of the two preceding terms), but when we reach positions divisible by 4, we apply an additional multiplication by $r$ to that sum. Answer C correctly captures this: $F_n = r(F_{n-1} + F_{n-2})$ when $n \equiv 0 \pmod{4}$ , and $F_n = F_{n-1} + F_{n-2}$ otherwise. This means we first compute the normal Fibonacci sum, then multiply the entire result by $r$ at every 4th position. Answer A is algebraically incorrect because it rearranges to $0 = (r-1)F_n$ , which would force $F_n = 0$ when $r > 1$ . Answer B uses assignment notation ( $\leftarrow$ ) rather than defining a recurrence relation, and doesn't properly specify the relationship between terms. Answer D incorrectly applies the factor $r$ only to $F_{n-2}$ rather than to the entire sum, which would create a fundamentally different sequence than described. Remember: when modifications are described as happening "to" a term after it's computed, look for the factor being applied to the entire expression that generates that term, not just to individual components within the recurrence.
A manufacturing process produces items in batches. The number of items in batch $n$ equals 90% of the items in batch $n-1$ , plus 60% of the items in batch $n-2$ (representing rework from two batches ago), minus a quality control removal of 50 items. However, production cannot go below 100 items per batch due to fixed overhead costs. If $I_n$ represents items in batch $n$ , which recurrence relation is appropriate for $n \geq 2$ ?
Answer: $I_n = \max(0.9I_{n-1} + 0.6I_{n-2} - 50, 100)$ for $n \geq 2$ When dealing with recurrence relations that involve constraints or minimum/maximum conditions, you need to carefully translate each business rule into mathematical language. This problem combines a standard linear recurrence with a floor constraint. The correct answer is C: $I_n = \max(0.9I_{n-1} + 0.6I_{n-2} - 50, 100)$ . This captures the manufacturing process perfectly: first calculate the natural production level (90% of previous batch plus 60% rework minus 50 removed items), then apply the minimum constraint of 100 items using the max function. The $\max$ operation elegantly handles both cases—when natural production exceeds 100, it uses that value; when it falls below 100, it enforces the minimum. Option A incorrectly uses $\min$ within the subtraction term, creating a convoluted expression that doesn't properly model the constraint. The nested $\min$ function makes the formula subtract a variable amount rather than applying a floor constraint. Option B uses conditional logic ("if...otherwise") which, while mathematically equivalent to option C, isn't written as a single recurrence relation formula. In discrete math, we prefer closed-form expressions using standard functions like $\max$ and $\min$ . Option D misunderstands the problem by applying minimums to individual terms ( $\max(0.9I_{n-1}, 90)$ ) rather than to the final result. This incorrectly suggests each component has its own constraint, which isn't stated in the problem. Study tip: When translating word problems into recurrence relations, identify constraints separately from the basic recurrence, then use $\max$ / $\min$ functions to enforce those constraints on the entire expression.
A company's monthly revenue follows a pattern where the revenue in month $n$ is the average of the revenues in the previous two months, plus a seasonal adjustment equal to half the revenue from three months ago. If $R_n$ represents revenue in month $n$ , which recurrence relation describes this pattern?
Answer: $R_n = \frac{R_{n-1} + R_{n-2}}{2} + \frac{R_{n-3}}{2}$ for $n \geq 3$ The revenue consists of two parts: (1) the average of the previous two months' revenues, which is $\frac{R_{n-1} + R_{n-2}}{2}$ , and (2) a seasonal adjustment equal to half the revenue from three months ago, which is $\frac{R_{n-3}}{2}$ . Therefore, $R_n = \frac{R_{n-1} + R_{n-2}}{2} + \frac{R_{n-3}}{2}$ . Choice B incorrectly averages all three terms together. Choice C uses the wrong denominator for the first part. Choice D omits the averaging operation for the first two terms.
A recursive algorithm for computing factorials uses the following approach: to compute $n!$ , it makes one recursive call to compute $(n-1)!$ , then performs $n$ multiplication operations to get the final result. Let $M(n)$ be the total number of multiplication operations needed to compute $n!$ using this algorithm. Which recurrence relation describes $M(n)$ ?
Answer: $M(n) = M(n-1) + n$ for $n \geq 1$ When analyzing recursive algorithms, you need to carefully track what operations happen at each level of recursion. The key is understanding that the recurrence relation must capture both the work done in the recursive call and the additional work done at the current level. Let's trace through this factorial algorithm. To compute $n!$ , the algorithm first makes a recursive call to compute $(n-1)!$ , which requires $M(n-1)$ multiplication operations. Then, according to the problem statement, it performs $n$ additional multiplication operations to get the final result. Therefore, the total number of multiplications is $M(n) = M(n-1) + n$ . Choice A suggests $M(n) = M(n-1) + n - 1$ , which incorrectly assumes only $n-1$ additional multiplications are needed at each step. This misinterprets the problem statement. Choice B gives $M(n) = M(n-1) + 1$ , indicating only one additional multiplication per recursive call. This would be correct if you were multiplying the result of $(n-1)!$ by $n$ once, but contradicts the stated $n$ operations. Choice C proposes $M(n) = nM(n-1) + 1$ , which would mean the number of operations grows exponentially. This misunderstands the relationship between recursive levels—you're not repeating the previous work $n$ times. The correct answer is D: $M(n) = M(n-1) + n$ . Study tip: When setting up recurrence relations, always identify two components: the cost of the recursive call(s) and the additional work done at the current level. Add these together carefully, paying close attention to the exact wording of how much work each step requires.
A supply chain model tracks inventory levels where each period's inventory equals 95% of the previous period's inventory (accounting for spoilage), plus 110% of the inventory from two periods ago (representing delayed restocking), minus a base consumption of 100 units. Additionally, if the resulting inventory would be negative, emergency procurement brings it up to exactly 50 units. If $I_n$ represents inventory in period $n$ , which recurrence relation correctly models this for $n \geq 2$ ?
Answer: $I_n = 0.95I_{n-1} + 1.1I_{n-2} - 100$ if result $\geq 0$ , otherwise $I_n = 50$ Emergency procurement sets inventory to exactly 50 when the calculated value would be negative, not when it's below 50. Choice A incorrectly ensures inventory is at least 50 always. Choice B correctly implements the negative threshold condition. Choice C always adds 50. Choice D attempts to adjust consumption, which is incorrect.
A viral video's view count follows a complex pattern: each day, it gains 150% of the previous day's views plus 80% of the views from two days ago, representing both direct sharing and delayed discovery. However, platform algorithms throttle viral content, so if the total calculated views would exceed 1 million, the actual views become the square root of the calculated amount (in thousands) times 1000. If $V_n$ represents views on day $n$ (in thousands), which recurrence relation is correct for $n \geq 2$ ?
Answer: Let $X = 1.5V_{n-1} + 0.8V_{n-2}$ . Then $V_n = X$ if $X \leq 1000$ , otherwise $V_n = 1000\sqrt{\frac{X}{1000}}$ When calculated views exceed 1000 (thousand), the actual views become $\sqrt{X/1000} \times 1000 = 1000\sqrt{X/1000}$ where $X$ is in thousands. Choice B correctly implements this transformation. Choice A uses min incorrectly. Choice C factors incorrectly. Choice D omits the division by 1000 inside the square root.
A learning algorithm adjusts weights according to this rule: the new weight is 120% of the previous weight, minus 30% of the weight from two iterations ago, plus an adjustment factor. The adjustment factor equals 10% of the current weight if the algorithm is converging (when consecutive weights are getting closer), otherwise it equals 5% of the previous weight. If $W_n$ denotes the weight after $n$ iterations, which recurrence relation correctly captures this for $n \geq 2$ ?
Answer: $W_n = 1.2W_{n-1} - 0.3W_{n-2} + 0.1(1.2W_{n-1} - 0.3W_{n-2})$ if $|W_{n-1} - W_{n-2}| < |W_{n-2} - W_{n-3}|$ , else $W_n = 1.2W_{n-1} - 0.3W_{n-2} + 0.05W_{n-1}$ When converging, adjustment is 10% of current weight (the calculated base value). Choice A creates circular reference using $W_n$ . Choice B correctly uses 10% of the calculated base weight $1.2W_{n-1} - 0.3W_{n-2}$ . Choice C combines terms incorrectly. Choice D uses 10% of previous weight instead of current calculated weight.
In a tournament bracket, teams are eliminated in pairs, with the winner advancing to the next round. However, in each round, one additional team receives a "bye" and automatically advances without playing. If $T_n$ represents the number of teams remaining after $n$ rounds, and initially there are $T_0$ teams, which recurrence relation models this situation?
Answer: $T_n = \frac{T_{n-1} - 1}{2} + 1$ for $n \geq 1$ When you encounter tournament bracket problems, focus on carefully tracking what happens to teams in each round. You need to identify how many teams are eliminated versus how many advance. Let's think through one round systematically. If you start with $T_{n-1}$ teams, one team gets a bye and automatically advances. The remaining $T_{n-1} - 1$ teams must pair up and play matches. Since teams are eliminated in pairs, you need $\frac{T_{n-1} - 1}{2}$ matches, which eliminates exactly $\frac{T_{n-1} - 1}{2}$ teams (one loser per match). The winners of these matches, plus the team with the bye, advance to the next round. So: $T_n = \frac{T_{n-1} - 1}{2} + 1$ , which is answer choice D. Choice A represents the number of teams eliminated rather than remaining - it's calculating $T_{n-1}$ minus the eliminated teams, but this just gives you the same result through subtraction instead of direct counting. Choice B assumes half the original teams advance plus one bye, but this ignores that the bye team comes from the original pool, not in addition to it. Choice C treats the bye as splitting the total in half, as if you're dividing all teams plus one extra, which doesn't reflect the actual tournament mechanics. When solving recurrence relations for elimination tournaments, always account for byes by first removing them from the competing pool, then calculating matches from the remaining teams. This prevents double-counting the bye recipients.
A population of bacteria doubles every hour, but at the end of each hour, exactly 100 bacteria are removed for testing. If $P_n$ represents the population after $n$ hours and the initial population is $P_0$ , which recurrence relation correctly models this situation?
Answer: $P_n = 2P_{n-1} - 100$ for $n \geq 1$ The bacteria first double (multiply by 2), then 100 are removed. So $P_n = 2P_{n-1} - 100$ . Choice B removes bacteria first, then doubles. Choice C is equivalent to A but unnecessarily complex. Choice D removes 100 times the previous population, not just 100 bacteria.

Start this quiz