A lab experiment measures the number of organisms at 8 am every day. Starting with 2 organisms on the first day, the number of organisms on any day is equal to 3 more than twice the number on the previous day. If the number of organisms on the nth day exceeds one million, then the lowest possible value of n is

Options

1. 20
2. 15
3. 25
4. 19

Correct Answer

19

Explanation

Given: O_1 = 2 O_n = 2 * O_(n-1) + 3, for n ≥ 2 We want the smallest n such that O_n > 1,000,000. Step 2: Solve the recurrence This is a linear recurrence: O_n = 2 * O_(n-1) + 3 The general solution is: O_n = A * 2^(n-1) + B Substitute into the recurrence: A * 2^(n-1) + B = 2 * (A * 2^(n-2) + B) + 3 A * 2^(n-1) + B = A * 2^(n-1) + 2B + 3 Solve for B: B = 2B + 3 -B = 3 B = -3 Now use the initial condition O_1 = 2: O_1 = A * 2^0 - 3 = A - 3 = 2 A = 5 So the closed-form formula is: O_n = 5 * 2^(n-1) - 3 Step 3: Solve for n such that O_n > 1,000,000 5 * 2^(n-1) - 3 > 1,000,000 5 * 2^(n-1) > 1,000,003 2^(n-1) > 200,000.6 Approximate powers of 2: 2^17 = 131,072 2^18 = 262,144 So n - 1 > 17.6 → n > 18.6 Since n must be an integer, the smallest n = 19. Answer: 19

← More CAT PYQs