Discrete Math Quiz: Formulating Recurrences
20 questions · exam conditions
0:00
Formulating RecurrencesQuestion 1 of 20

A recursive algorithm for computing factorials uses the following approach: to compute n!n!, it makes one recursive call to compute (n−1)!(n-1)!, then performs nn multiplication operations to get the final result. Let M(n)M(n) be the total number of multiplication operations needed to compute n!n! using this algorithm. Which recurrence relation describes M(n)M(n)?

M(n)=M(n−1)+n−1M(n) = M(n-1) + n - 1 for n≥1n \geq 1
M(n)=M(n−1)+1M(n) = M(n-1) + 1 for n≥1n \geq 1
M(n)=nM(n−1)+1M(n) = nM(n-1) + 1 for n≥1n \geq 1
M(n)=M(n−1)+nM(n) = M(n-1) + n for n≥1n \geq 1
← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Formulating Recurrences

Practice Formulating Recurrences in Discrete Math with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Formulating Recurrences, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

A recursive algorithm for computing factorials uses the following approach: to compute n!n!, it makes one recursive call to compute (n−1)!(n-1)!, then performs nn multiplication operations to get the final result. Let M(n)M(n) be the total number of multiplication operations needed to compute n!n! using this algorithm. Which recurrence relation describes M(n)M(n)?

  1. M(n)=M(n−1)+n−1M(n) = M(n-1) + n - 1 for n≥1n \geq 1
  2. M(n)=M(n−1)+1M(n) = M(n-1) + 1 for n≥1n \geq 1
  3. M(n)=nM(n−1)+1M(n) = nM(n-1) + 1 for n≥1n \geq 1
  4. M(n)=M(n−1)+nM(n) = M(n-1) + n for n≥1n \geq 1 (correct answer)
Explanation: 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!n!, the algorithm first makes a recursive call to compute (n−1)!(n-1)!, which requires M(n−1)M(n-1) multiplication operations. Then, according to the problem statement, it performs nn additional multiplication operations to get the final result. Therefore, the total number of multiplications is M(n)=M(n−1)+nM(n) = M(n-1) + n. Choice A suggests M(n)=M(n−1)+n−1M(n) = M(n-1) + n - 1, which incorrectly assumes only n−1n-1 additional multiplications are needed at each step. This misinterprets the problem statement. Choice B gives M(n)=M(n−1)+1M(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)!(n-1)! by nn once, but contradicts the stated nn operations. Choice C proposes M(n)=nM(n−1)+1M(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 nn times. The correct answer is D: M(n)=M(n−1)+nM(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.

Question 2

A population of bacteria doubles every hour, but at the end of each hour, exactly 100 bacteria are removed for testing. If PnP_n represents the population after nn hours and the initial population is P0P_0, which recurrence relation correctly models this situation?

  1. Pn=2Pn−1−100P_n = 2P_{n-1} - 100 for n≥1n \geq 1 (correct answer)
  2. Pn=2(Pn−1−100)P_n = 2(P_{n-1} - 100) for n≥1n \geq 1
  3. Pn=Pn−1+2Pn−1−100P_n = P_{n-1} + 2P_{n-1} - 100 for n≥1n \geq 1
  4. Pn=2Pn−1−100Pn−1P_n = 2P_{n-1} - 100P_{n-1} for n≥1n \geq 1
Explanation: The bacteria first double (multiply by 2), then 100 are removed. So Pn=2Pn−1−100P_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.

Question 3

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>1r > 1 to account for periodic external input. If FnF_n denotes the nn-th term of this modified sequence, which recurrence relation correctly describes it for n≥3n \geq 3?

  1. Fn=Fn−1+Fn−2+(r−1)FnF_n = F_{n-1} + F_{n-2} + (r-1)F_n if 4∣n4|n, otherwise Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2}
  2. Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2} for all nn, but Fn←r⋅FnF_n \leftarrow r \cdot F_n if n≡0(mod4)n \equiv 0 \pmod{4}
  3. Fn=r(Fn−1+Fn−2)F_n = r(F_{n-1} + F_{n-2}) if n≡0(mod4)n \equiv 0 \pmod{4}, otherwise Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2} (correct answer)
  4. Fn=Fn−1+r⋅Fn−2F_n = F_{n-1} + r \cdot F_{n-2} if n≡0(mod4)n \equiv 0 \pmod{4}, otherwise Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2}
Explanation: 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>1r > 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 rr to that sum. Answer C correctly captures this: Fn=r(Fn−1+Fn−2)F_n = r(F_{n-1} + F_{n-2}) when n≡0(mod4)n \equiv 0 \pmod{4}, and Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2} otherwise. This means we first compute the normal Fibonacci sum, then multiply the entire result by rr at every 4th position. Answer A is algebraically incorrect because it rearranges to 0=(r−1)Fn0 = (r-1)F_n, which would force Fn=0F_n = 0 when r>1r > 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 rr only to Fn−2F_{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.

Question 4

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 VnV_n represents views on day nn (in thousands), which recurrence relation is correct for n≥2n \geq 2?

  1. Vn=min⁡(1.5Vn−1+0.8Vn−2,10001.5Vn−1+0.8Vn−2)V_n = \min(1.5V_{n-1} + 0.8V_{n-2}, 1000\sqrt{1.5V_{n-1} + 0.8V_{n-2}}) for n≥2n \geq 2
  2. Let X=1.5Vn−1+0.8Vn−2X = 1.5V_{n-1} + 0.8V_{n-2}. Then Vn=XV_n = X if X≤1000X \leq 1000, otherwise Vn=1000X1000V_n = 1000\sqrt{\frac{X}{1000}} (correct answer)
  3. Vn=1.5Vn−1+0.8Vn−2V_n = 1.5V_{n-1} + 0.8V_{n-2} if 1.5Vn−1+0.8Vn−2≤10001.5V_{n-1} + 0.8V_{n-2} \leq 1000, else Vn=1000⋅1.5Vn−1+0.8Vn−2V_n = \sqrt{1000} \cdot \sqrt{1.5V_{n-1} + 0.8V_{n-2}}
  4. Vn=1.5Vn−1+0.8Vn−2V_n = 1.5V_{n-1} + 0.8V_{n-2} if 1.5Vn−1+0.8Vn−2≤10001.5V_{n-1} + 0.8V_{n-2} \leq 1000, else Vn=10001.5Vn−1+0.8Vn−2V_n = 1000\sqrt{1.5V_{n-1} + 0.8V_{n-2}}
Explanation: When calculated views exceed 1000 (thousand), the actual views become X/1000×1000=1000X/1000\sqrt{X/1000} \times 1000 = 1000\sqrt{X/1000} where XX 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.

Question 5

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 WnW_n represents the water level after nn minutes, which recurrence relation is correct for n≥2n \geq 2?

  1. Wn=0.85Wn−1+0.4Wn−2+20W_n = 0.85W_{n-1} + 0.4W_{n-2} + 20 if result ≤500\leq 500, otherwise solve Wn=500W_n = 500
  2. Wn=0.85Wn−1+0.4Wn−2+20−max⁡(0,0.85Wn−1+0.4Wn−2+20−500)W_n = 0.85W_{n-1} + 0.4W_{n-2} + 20 - \max(0, 0.85W_{n-1} + 0.4W_{n-2} + 20 - 500)
  3. Wn=0.85Wn−1+min⁡(0.4Wn−2,200)+20W_n = 0.85W_{n-1} + \min(0.4W_{n-2}, 200) + 20 for n≥2n \geq 2
  4. Wn=min⁡(0.85Wn−1+0.4Wn−2+20,500)W_n = \min(0.85W_{n-1} + 0.4W_{n-2} + 20, 500) for n≥2n \geq 2 (correct answer)
Explanation: 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.85Wn−10.85W_{n-1}), 40% flows back from two minutes ago (0.4Wn−20.4W_{n-2}), and 20 gallons flow in constantly. Without any capacity limit, this would give us Wn=0.85Wn−1+0.4Wn−2+20W_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 Wn=min⁡(0.85Wn−1+0.4Wn−2+20,500)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,...)\max(0, ...) term essentially recreates what min⁡\min already accomplishes more elegantly. Choice C incorrectly applies the capacity constraint to only the return flow component (0.4Wn−20.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⁡\min function to cap the maximum value. This is the standard mathematical way to express "up to a limit" relationships in discrete mathematics.

Question 6

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 $BnB_n representsthebalanceafterrepresents the balance after nn months,whichrecurrencerelationcorrectlymodelsthisscenarioformonths, which recurrence relation correctly models this scenario for n≥1n \geq 1 $?

  1. Bn=1.05(Bn−1−200)+500B_n = 1.05(B_{n-1} - 200) + 500 if n≡0(mod6)n \equiv 0 \pmod{6}, otherwise Bn=1.05(Bn−1−200)B_n = 1.05(B_{n-1} - 200) (correct answer)
  2. Bn=1.05Bn−1−200+500B_n = 1.05B_{n-1} - 200 + 500 if n≡0(mod6)n \equiv 0 \pmod{6}, otherwise Bn=1.05Bn−1−200B_n = 1.05B_{n-1} - 200
  3. Bn=(Bn−1−200)⋅1.05+500B_n = (B_{n-1} - 200) \cdot 1.05 + 500 if 6∣n6|n, otherwise Bn=(Bn−1−200)⋅1.05B_n = (B_{n-1} - 200) \cdot 1.05
  4. Bn=1.05Bn−1−210+500B_n = 1.05B_{n-1} - 210 + 500 if n≡0(mod6)n \equiv 0 \pmod{6}, otherwise Bn=1.05Bn−1−210B_n = 1.05B_{n-1} - 210
Explanation: 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).

Question 7

A manufacturing process produces items in batches. The number of items in batch nn equals 90% of the items in batch n−1n-1, plus 60% of the items in batch n−2n-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 InI_n represents items in batch nn, which recurrence relation is appropriate for n≥2n \geq 2?

  1. In=0.9In−1+0.6In−2−min⁡(50,0.9In−1+0.6In−2−100)I_n = 0.9I_{n-1} + 0.6I_{n-2} - \min(50, 0.9I_{n-1} + 0.6I_{n-2} - 100)
  2. In=0.9In−1+0.6In−2−50I_n = 0.9I_{n-1} + 0.6I_{n-2} - 50 if result ≥100\geq 100, otherwise In=100I_n = 100
  3. In=max⁡(0.9In−1+0.6In−2−50,100)I_n = \max(0.9I_{n-1} + 0.6I_{n-2} - 50, 100) for n≥2n \geq 2 (correct answer)
  4. In=max⁡(0.9In−1,90)+max⁡(0.6In−2,60)−50I_n = \max(0.9I_{n-1}, 90) + \max(0.6I_{n-2}, 60) - 50 for n≥2n \geq 2
Explanation: 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: In=max⁡(0.9In−1+0.6In−2−50,100)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⁡\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⁡\min within the subtraction term, creating a convoluted expression that doesn't properly model the constraint. The nested min⁡\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⁡\max and min⁡\min. Option D misunderstands the problem by applying minimums to individual terms (max⁡(0.9In−1,90)\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⁡\max/min⁡\min functions to enforce those constraints on the entire expression.

Question 8

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 WnW_n denotes the weight after nn iterations, which recurrence relation correctly captures this for n≥2n \geq 2?

  1. Wn=1.2Wn−1−0.3Wn−2+0.1WnW_n = 1.2W_{n-1} - 0.3W_{n-2} + 0.1W_n if ∣Wn−1−Wn−2∣<∣Wn−2−Wn−3∣|W_{n-1} - W_{n-2}| < |W_{n-2} - W_{n-3}|, else Wn=1.2Wn−1−0.3Wn−2+0.05Wn−1W_n = 1.2W_{n-1} - 0.3W_{n-2} + 0.05W_{n-1}
  2. Wn=1.2Wn−1−0.3Wn−2+0.1(1.2Wn−1−0.3Wn−2)W_n = 1.2W_{n-1} - 0.3W_{n-2} + 0.1(1.2W_{n-1} - 0.3W_{n-2}) if ∣Wn−1−Wn−2∣<∣Wn−2−Wn−3∣|W_{n-1} - W_{n-2}| < |W_{n-2} - W_{n-3}|, else Wn=1.2Wn−1−0.3Wn−2+0.05Wn−1W_n = 1.2W_{n-1} - 0.3W_{n-2} + 0.05W_{n-1} (correct answer)
  3. Wn=1.3Wn−1−0.3Wn−2W_n = 1.3W_{n-1} - 0.3W_{n-2} if ∣Wn−1−Wn−2∣<∣Wn−2−Wn−3∣|W_{n-1} - W_{n-2}| < |W_{n-2} - W_{n-3}|, else Wn=1.25Wn−1−0.3Wn−2W_n = 1.25W_{n-1} - 0.3W_{n-2}
  4. Wn=1.2Wn−1−0.3Wn−2+0.1Wn−1W_n = 1.2W_{n-1} - 0.3W_{n-2} + 0.1W_{n-1} if ∣Wn−1−Wn−2∣<∣Wn−2−Wn−3∣|W_{n-1} - W_{n-2}| < |W_{n-2} - W_{n-3}|, else Wn=1.2Wn−1−0.3Wn−2+0.05Wn−1W_n = 1.2W_{n-1} - 0.3W_{n-2} + 0.05W_{n-1}
Explanation: When converging, adjustment is 10% of current weight (the calculated base value). Choice A creates circular reference using WnW_n. Choice B correctly uses 10% of the calculated base weight 1.2Wn−1−0.3Wn−21.2W_{n-1} - 0.3W_{n-2}. Choice C combines terms incorrectly. Choice D uses 10% of previous weight instead of current calculated weight.

Question 9

A tower of blocks is built according to the following rules: to build a tower of height nn, you can either add a single block to a tower of height n−1n-1, or add two blocks simultaneously to a tower of height n−2n-2, but only if the tower of height n−2n-2 has an even number of ways to be constructed. If TnT_n represents the number of ways to build a tower of height nn, which recurrence relation is correct?

  1. Tn=Tn−1+Tn−2T_n = T_{n-1} + T_{n-2} if Tn−2T_{n-2} is even, otherwise Tn=Tn−1T_n = T_{n-1} (correct answer)
  2. Tn=Tn−1+2Tn−2T_n = T_{n-1} + 2T_{n-2} if Tn−2T_{n-2} is even, otherwise Tn=Tn−1T_n = T_{n-1}
  3. Tn=Tn−1+Tn−2T_n = T_{n-1} + T_{n-2} if n−2n-2 is even, otherwise Tn=Tn−1T_n = T_{n-1}
  4. Tn=Tn−1+1T_n = T_{n-1} + 1 if Tn−2T_{n-2} is even, otherwise Tn=Tn−1T_n = T_{n-1}
Explanation: You can always add one block (contributing Tn−1T_{n-1} ways). You can add two blocks only if Tn−2T_{n-2} is even, and this contributes Tn−2T_{n-2} additional ways. Choice B incorrectly doubles Tn−2T_{n-2}. Choice C checks if n−2n-2 is even rather than Tn−2T_{n-2}. Choice D adds only 1 way instead of Tn−2T_{n-2} ways.

Question 10

A recursive sequence models population growth where each generation is 80% of the previous generation plus 40% of the generation before that, representing both survival and delayed reproduction. However, environmental constraints limit the population such that if the calculated value exceeds the carrying capacity KK, the actual population becomes K−(excess)/2K - (\text{excess})/2. If PnP_n represents the population in generation nn, which recurrence relation is correct for n≥2n \geq 2?

  1. Pn=min⁡(0.8Pn−1+0.4Pn−2,K−0.8Pn−1+0.4Pn−2−K2)P_n = \min(0.8P_{n-1} + 0.4P_{n-2}, K - \frac{0.8P_{n-1} + 0.4P_{n-2} - K}{2})
  2. Let X=0.8Pn−1+0.4Pn−2X = 0.8P_{n-1} + 0.4P_{n-2}. Then Pn=XP_n = X if X≤KX \leq K, otherwise Pn=K−X−K2P_n = K - \frac{X-K}{2} (correct answer)
  3. Pn=0.8Pn−1+0.4Pn−2P_n = 0.8P_{n-1} + 0.4P_{n-2} if 0.8Pn−1+0.4Pn−2≤K0.8P_{n-1} + 0.4P_{n-2} \leq K, otherwise Pn=K2P_n = \frac{K}{2}
  4. Pn=min⁡(0.8Pn−1+0.4Pn−2,K)−max⁡(0,0.8Pn−1+0.4Pn−2−K)/2P_n = \min(0.8P_{n-1} + 0.4P_{n-2}, K) - \max(0, 0.8P_{n-1} + 0.4P_{n-2} - K)/2
Explanation: When the calculated value XX exceeds KK, the population becomes KK minus half the excess, which is K−(X−K)/2K - (X-K)/2. Choice A uses min incorrectly. Choice B correctly implements the piecewise function. Choice C sets population to K/2K/2 instead of the correct formula. Choice D subtracts the excess adjustment from the minimum, which is incorrect.

Question 11

A digital signal processing system applies the following transformation: each sample SnS_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 SnS_n represents the nn-th processed sample, which recurrence relation correctly models this for n≥2n \geq 2?

  1. Sn=0.6∣Sn−1∣+0.25∣Sn−2∣+0.15∣Sn−1−Sn−2∣S_n = 0.6|S_{n-1}| + 0.25|S_{n-2}| + 0.15|S_{n-1} - S_{n-2}| for n≥2n \geq 2
  2. Sn=0.6Sn−1+0.25Sn−2−0.15∣Sn−1−Sn−2∣S_n = 0.6S_{n-1} + 0.25S_{n-2} - 0.15|S_{n-1} - S_{n-2}| for n≥2n \geq 2
  3. Sn=0.6Sn−1+0.25Sn−2+0.15(Sn−1−Sn−2)S_n = 0.6S_{n-1} + 0.25S_{n-2} + 0.15(S_{n-1} - S_{n-2}) for n≥2n \geq 2
  4. Sn=0.6Sn−1+0.25Sn−2+0.15∣Sn−1−Sn−2∣S_n = 0.6S_{n-1} + 0.25S_{n-2} + 0.15|S_{n-1} - S_{n-2}| for n≥2n \geq 2 (correct answer)
Explanation: 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 SnS_n consists of three components: 60% of the previous sample (0.6Sn−10.6S_{n-1}), plus 25% of the sample from two steps back (0.25Sn−20.25S_{n-2}), plus a noise reduction term equal to 15% of the absolute difference between those two previous samples (0.15∣Sn−1−Sn−2∣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 Sn=0.6Sn−1+0.25Sn−2+0.15∣Sn−1−Sn−2∣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 Sn−1S_{n-1} and Sn−2S_{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.

Question 12

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 InI_n represents inventory in period nn, which recurrence relation correctly models this for n≥2n \geq 2?

  1. In=max⁡(0.95In−1+1.1In−2−100,50)I_n = \max(0.95I_{n-1} + 1.1I_{n-2} - 100, 50) for n≥2n \geq 2
  2. In=0.95In−1+1.1In−2−100I_n = 0.95I_{n-1} + 1.1I_{n-2} - 100 if result ≥0\geq 0, otherwise In=50I_n = 50 (correct answer)
  3. In=max⁡(0.95In−1+1.1In−2−100,0)+50I_n = \max(0.95I_{n-1} + 1.1I_{n-2} - 100, 0) + 50 for n≥2n \geq 2
  4. In=0.95In−1+1.1In−2−min⁡(100,0.95In−1+1.1In−2−50)I_n = 0.95I_{n-1} + 1.1I_{n-2} - \min(100, 0.95I_{n-1} + 1.1I_{n-2} - 50)
Explanation: 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.

Question 13

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 TT, the platform's algorithm boosts it by adding 50% of the threshold value. If EnE_n represents engagement on day nn, which recurrence relation correctly models this for n≥2n \geq 2?

  1. En=0.7En−1+0.3En−2E_n = 0.7E_{n-1} + 0.3E_{n-2} if result ≥T\geq T, otherwise En=1.5TE_n = 1.5T
  2. En=0.7En−1+0.3En−2+0.5TE_n = 0.7E_{n-1} + 0.3E_{n-2} + 0.5T if En−1<TE_{n-1} < T, otherwise En=0.7En−1+0.3En−2E_n = 0.7E_{n-1} + 0.3E_{n-2}
  3. En=max⁡(0.7En−1+0.3En−2,T+0.5T)E_n = \max(0.7E_{n-1} + 0.3E_{n-2}, T + 0.5T) for n≥2n \geq 2
  4. En=0.7En−1+0.3En−2+0.5TE_n = 0.7E_{n-1} + 0.3E_{n-2} + 0.5T if 0.7En−1+0.3En−2<T0.7E_{n-1} + 0.3E_{n-2} < T, otherwise En=0.7En−1+0.3En−2E_n = 0.7E_{n-1} + 0.3E_{n-2} (correct answer)
Explanation: 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.7En−1+0.3En−20.7E_{n-1} + 0.3E_{n-2}. Then, if this result falls below threshold TT, the algorithm adds 50% of TT as a boost. Option D correctly captures this two-step process. It calculates the base engagement, checks if it's below TT, and if so, adds 0.5T0.5T to boost it. Otherwise, it uses just the base calculation. Option A incorrectly replaces the entire engagement with 1.5T1.5T when below threshold, ignoring the original calculation completely. Option B has the wrong trigger condition—it checks if En−1<TE_{n-1} < T (yesterday's engagement) rather than checking if today's calculated value is below TT. Option C uses max⁡(0.7En−1+0.3En−2,T+0.5T)\max(0.7E_{n-1} + 0.3E_{n-2}, T + 0.5T), which would set engagement to 1.5T1.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.

Question 14

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 $PnP_n representstheprofitinmonthrepresents the profit in month nn ,whichrecurrencerelationmodelsthissituationfor, which recurrence relation models this situation for n≥2n \geq 2 $?

  1. Pn=1.2Pn−1−5000+0.1(1.2Pn−1)P_n = 1.2P_{n-1} - 5000 + 0.1(1.2P_{n-1}) if n≡0(mod3)n \equiv 0 \pmod{3}, otherwise Pn=1.2Pn−1−5000P_n = 1.2P_{n-1} - 5000
  2. Pn=1.2Pn−1−5000+0.1Pn−1P_n = 1.2P_{n-1} - 5000 + 0.1P_{n-1} if n≡0(mod3)n \equiv 0 \pmod{3}, otherwise Pn=1.2Pn−1−5000P_n = 1.2P_{n-1} - 5000
  3. Pn=1.32Pn−1−5000P_n = 1.32P_{n-1} - 5000 if n≡0(mod3)n \equiv 0 \pmod{3}, otherwise Pn=1.2Pn−1−5000P_n = 1.2P_{n-1} - 5000 (correct answer)
  4. Pn=1.2Pn−1−5000+0.1PnP_n = 1.2P_{n-1} - 5000 + 0.1P_n if n≡0(mod3)n \equiv 0 \pmod{3}, otherwise Pn=1.2Pn−1−5000P_n = 1.2P_{n-1} - 5000
Explanation: 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.2Pn−11.2P_{n-1}). This gives 1.2Pn−1+0.1(1.2Pn−1)=1.32Pn−11.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 PnP_n on both sides.

Question 15

A sequence is defined where each term equals three times the previous term minus twice the term before that, with initial conditions a1=2a_1 = 2 and a2=5a_2 = 5. Additionally, every third term is increased by 1. If ana_n denotes the nn-th term for n≥3n \geq 3, which recurrence relation correctly captures this pattern?

  1. an=3an−1−2an−2+1a_n = 3a_{n-1} - 2a_{n-2} + 1 if n≡0(mod3)n \equiv 0 \pmod{3}, otherwise an=3an−1−2an−2a_n = 3a_{n-1} - 2a_{n-2} (correct answer)
  2. an=3an−1−2an−2+1a_n = 3a_{n-1} - 2a_{n-2} + 1 if n≡1(mod3)n \equiv 1 \pmod{3}, otherwise an=3an−1−2an−2a_n = 3a_{n-1} - 2a_{n-2}
  3. an=3an−1−2an−2a_n = 3a_{n-1} - 2a_{n-2} for all n≥3n \geq 3, with a3=a3+1a_3 = a_3 + 1
  4. an=3an−1−2an−2+[n mod 3=0]a_n = 3a_{n-1} - 2a_{n-2} + [n \bmod 3 = 0] for n≥3n \geq 3
Explanation: Every third term means terms at positions 3, 6, 9, etc., which are positions where n≡0(mod3)n \equiv 0 \pmod{3}. Choice B incorrectly uses n≡1(mod3)n \equiv 1 \pmod{3}. Choice C is incomplete notation. Choice D uses bracket notation incorrectly for the modular condition.

Question 16

In a computer network, the number of active connections in hour nn depends on the previous two hours as follows: half of the connections from hour n−1n-1 remain active, plus one-third of the connections from hour n−2n-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 CnC_n, the number of connections in hour nn?

  1. Cn=min⁡(12Cn−1+13Cn−2+50,1000)C_n = \min(\frac{1}{2}C_{n-1} + \frac{1}{3}C_{n-2} + 50, 1000) for n≥2n \geq 2 (correct answer)
  2. Cn=12Cn−1+13Cn−2+50C_n = \frac{1}{2}C_{n-1} + \frac{1}{3}C_{n-2} + 50 if Cn≤1000C_n \leq 1000, otherwise Cn=1000C_n = 1000
  3. Cn=12Cn−1+13Cn−2+min⁡(50,1000−Cn)C_n = \frac{1}{2}C_{n-1} + \frac{1}{3}C_{n-2} + \min(50, 1000-C_n) for n≥2n \geq 2
  4. Cn=min⁡(12Cn−1,500)+min⁡(13Cn−2,333)+50C_n = \min(\frac{1}{2}C_{n-1}, 500) + \min(\frac{1}{3}C_{n-2}, 333) + 50 for n≥2n \geq 2
Explanation: The formula calculates the total connections, then caps at 1000 using min function. Choice B uses circular logic (CnC_n appears on both sides of condition). Choice C creates circular reference with CnC_n in the min function. Choice D incorrectly caps individual components rather than the total.

Question 17

A sequence of binary strings is defined such that each string of length nn must not contain three consecutive 1's. Let f(n)f(n) be the number of valid binary strings of length nn. Which recurrence relation correctly describes f(n)f(n)?

  1. f(n)=f(n−1)+f(n−2)+f(n−3)f(n) = f(n-1) + f(n-2) + f(n-3) for n≥3n \geq 3 (correct answer)
  2. f(n)=2f(n−1)−f(n−2)−f(n−3)f(n) = 2f(n-1) - f(n-2) - f(n-3) for n≥3n \geq 3
  3. f(n)=f(n−1)+f(n−2)+f(n−4)f(n) = f(n-1) + f(n-2) + f(n-4) for n≥4n \geq 4
  4. f(n)=2f(n−1)−f(n−3)f(n) = 2f(n-1) - f(n-3) for n≥3n \geq 3
Explanation: Consider valid strings of length nn. Case 1: strings ending in 0 - there are f(n−1)f(n-1) such strings. Case 2: strings ending in 10 - there are f(n−2)f(n-2) such strings. Case 3: strings ending in 110 - there are f(n−3)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)f(n) = f(n-1) + f(n-2) + f(n-3). Choice B uses incorrect coefficients. Choice C omits the f(n−3)f(n-3) term and adds an irrelevant f(n−4)f(n-4) term. Choice D has the wrong structure entirely.

Question 18

A manufacturing process produces items in batches. The number of defective items in batch nn 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 DnD_n represents defective items in batch nn, which recurrence relation captures this relationship?

  1. Dn=Dn−1+Dn−22D_n = \sqrt{D_{n-1}} + \frac{D_{n-2}}{2} for n≥2n \geq 2
  2. Dn=Dn−1+5⋅Dn−210D_n = \sqrt{D_{n-1}} + 5 \cdot \frac{D_{n-2}}{10} for n≥2n \geq 2 (correct answer)
  3. Dn=Dn−1+5Dn−210D_n = \sqrt{D_{n-1}} + \frac{5D_{n-2}}{10} for n≥2n \geq 2
  4. Dn=Dn−1+5Dn−2D_n = \sqrt{D_{n-1}} + 5D_{n-2} for n≥2n \geq 2
Explanation: The defective items consist of: (1) an amount proportional to Dn−1\sqrt{D_{n-1}} (with proportionality constant 1), and (2) an increase of 5 for every 10 defective items in batch n−2n-2. The second part means we add 5×Dn−2105 \times \frac{D_{n-2}}{10}. Therefore Dn=Dn−1+5⋅Dn−210D_n = \sqrt{D_{n-1}} + 5 \cdot \frac{D_{n-2}}{10}. Choice A uses 12\frac{1}{2} instead of 510\frac{5}{10}. Choice C writes the expression as 5Dn−210\frac{5D_{n-2}}{10} which equals Dn−22\frac{D_{n-2}}{2}, missing the factor of 5. Choice D uses 5Dn−25D_{n-2} instead of 5⋅Dn−2105 \cdot \frac{D_{n-2}}{10}.

Question 19

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 TnT_n represents the number of teams remaining after nn rounds, and initially there are T0T_0 teams, which recurrence relation models this situation?

  1. Tn=Tn−1−Tn−1−12T_n = T_{n-1} - \frac{T_{n-1} - 1}{2} for n≥1n \geq 1
  2. Tn=Tn−12+1T_n = \frac{T_{n-1}}{2} + 1 for n≥1n \geq 1
  3. Tn=Tn−1+12T_n = \frac{T_{n-1} + 1}{2} for n≥1n \geq 1
  4. Tn=Tn−1−12+1T_n = \frac{T_{n-1} - 1}{2} + 1 for n≥1n \geq 1 (correct answer)
Explanation: 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 Tn−1T_{n-1} teams, one team gets a bye and automatically advances. The remaining Tn−1−1T_{n-1} - 1 teams must pair up and play matches. Since teams are eliminated in pairs, you need Tn−1−12\frac{T_{n-1} - 1}{2} matches, which eliminates exactly Tn−1−12\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: Tn=Tn−1−12+1T_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 Tn−1T_{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.

Question 20

A computer virus spreads through a network such that on day nn, the number of newly infected computers is equal to twice the number of computers that were infected on day n−1n-1, plus three times the number of computers that were infected on day n−2n-2. If ana_n represents the total number of infected computers by the end of day nn, which recurrence relation correctly models this situation?

  1. an=2an−1+3an−2a_n = 2a_{n-1} + 3a_{n-2} for n≥2n \geq 2
  2. an=an−1+2an−1+3an−2a_n = a_{n-1} + 2a_{n-1} + 3a_{n-2} for n≥2n \geq 2
  3. an=an−1+2(an−1−an−2)+3(an−2−an−3)a_n = a_{n-1} + 2(a_{n-1} - a_{n-2}) + 3(a_{n-2} - a_{n-3}) for n≥3n \geq 3 (correct answer)
  4. an=an−1+2an−1+3an−2−an−3a_n = a_{n-1} + 2a_{n-1} + 3a_{n-2} - a_{n-3} for n≥3n \geq 3
Explanation: The key insight is that ana_n represents the total number of infected computers, not just newly infected ones. The newly infected computers on day nn is 2(an−1−an−2)+3(an−2−an−3)2(a_{n-1} - a_{n-2}) + 3(a_{n-2} - a_{n-3}), where an−1−an−2a_{n-1} - a_{n-2} represents computers infected on day n−1n-1 and an−2−an−3a_{n-2} - a_{n-3} represents computers infected on day n−2n-2. Therefore, an=an−1+2(an−1−an−2)+3(an−2−an−3)a_n = a_{n-1} + 2(a_{n-1} - a_{n-2}) + 3(a_{n-2} - a_{n-3}). Choice A incorrectly treats ana_n as newly infected computers. Choice B simplifies incorrectly to an=3an−1+3an−2a_n = 3a_{n-1} + 3a_{n-2}. Choice D has an incorrect subtraction term.