Recurrence Practice Questions

Given recurrence relations:
$f(1) = 1$
$f(2n) = 2f(n) - 1$ for $n \ge 1$
$f(2n+1) = 2f(n) + 1$ for $n \ge 1$

Let's compute some values:
$f(1) = 1$
$f(2) = 2f(1) - 1 = 2(1) - 1 = 1$ (for $n=1$)
$f(3) = 2f(1) + 1 = 2(1) + 1 = 3$ (for $n=1$)
$f(4) = 2f(2) - 1 = 2(1) - 1 = 1$ (for $n=2$)
$f(5) = 2f(2) + 1 = 2(1) + 1 = 3$ (for $n=2$)
$f(6) = 2f(3) - 1 = 2(3) - 1 = 5$ (for $n=3$)
$f(7) = 2f(3) + 1 = 2(3) + 1 = 7$ (for $n=3$)
$f(8) = 2f(4) - 1 = 2(1) - 1 = 1$ (for $n=4$)

Observe a pattern:
$f(2^k) = 1$ for $k \ge 0$. (e.g., $f(1)=1, f(2)=1, f(4)=1, f(8)=1$)
$f(2^k-1) = 2^k-1$. (e.g., $f(1)=1, f(3)=3, f(7)=7$)

Let's test the statements:
(A) "$f(2^n-1) = 2^n-1$"
Base case: $n=1$, $f(2^{1-}1)=f(1)=1$. $2^{1-}1=1$. True.
Assume $f(2^k-1) = 2^k-1$ for some $k \ge 1$.
We need to show $f(2^{k+1}-1) = 2^{k+1}-1$.
$2^{k+1}-1$ is an odd number. Let $m=2^k-1$. Then $2^{k+1}-1 = 2(2^k-1)+1$. So $f(2m+1) = 2f(m)+1$.
$f(2^{k+1}-1) = f(2(2^k-1)+1) = 2f(2^k-1) + 1$.
By induction hypothesis, $f(2^k-1) = 2^k-1$.
So, $f(2^{k+1}-1) = 2(2^k-1) + 1 = 2^{k+1} - 2 + 1 = 2^{k+1} - 1$.
This statement is TRUE.

(B) "$f(2^n) = 1$"
Base case: $n=1$, $f(2^1)=f(2)=1$. True.
Assume $f(2^k) = 1$ for some $k \ge 1$.
We need to show $f(2^{k+1}) = 1$.
$f(2^{k+1}) = f(2 \cdot 2^k) = 2f(2^k) - 1$.
By induction hypothesis, $f(2^k) = 1$.
So, $f(2^{k+1}) = 2(1) - 1 = 1$.
This statement is TRUE.

(C) "$f(5 \cdot 2^n) = 2^{n+1}+1$"
Let's test with small $n$:
For $n=0$: $f(5 \cdot 2^0) = f(5) = 3$.
According to the formula: $2^{0+1}+1 = 2^{1+}1 = 3$. True for $n=0$.
For $n=1$: $f(5 \cdot 2^1) = f(10)$.
$f(10) = 2f(5) - 1 = 2(3) - 1 = 5$.
According to the formula: $2^{1+1}+1 = 2^{2+}1 = 5$. True for $n=1$.
For $n=2$: $f(5 \cdot 2^2) = f(20)$.
$f(20) = 2f(10) - 1 = 2(5) - 1 = 9$.
According to the formula: $2^{2+1}+1 = 2^{3+}1 = 9$. True for $n=2$.
This statement appears to be TRUE. (This can be proven by induction as well.)
Let $x = 5 \cdot 2^n$. $f(x) = f(2 \cdot (5 \cdot 2^{n-1})) = 2 f(5 \cdot 2^{n-1}) - 1$.
This forms a sequence $a_n = 2a_{n-1} - 1$.
If $a_0 = f(5) = 3$.
$a_n = C \cdot 2^n + D$. $3 = C+D$.
$D = 2D - 1 \Rightarrow D=1$.
$C+1 = 3 \Rightarrow C=2$.
So $f(5 \cdot 2^n) = 2 \cdot 2^n + 1 = 2^{n+1} + 1$.
This statement is TRUE.

(D) "$f(2^n+1) = 2^n+1$"
Let's test with small $n$:
For $n=1$: $f(2^{1+}1) = f(3) = 3$. Formula: $2^{1+}1 = 3$. True.
For $n=2$: $f(2^{2+}1) = f(5) = 3$. Formula: $2^{2+}1 = 5$. So $3 \neq 5$.
This statement is FALSE.

The TRUE statements are (A), (B), and (C).

The recurrence relation is $a_{n}=6n^{2}+2n+a_{n-1}$ with $a_1 = 8$. By expanding the relation for $a_{99}$, we get $a_{99} = \sum_{i=2}^{99} (6i^2 + 2i) + a_1$. We can observe that the initial condition $a_1 = 8$ is equal to $6(1^2) + 2(1)$. Therefore, the expression for $a_{99}$ can be written as a complete sum from $i=1$: $a_{99} = \sum_{i=1}^{99} (6i^2 + 2i)$. Using the formulas for the sum of the first $k$ integers and squares, this evaluates to $9900 \times (199+1) = 1980000 = 198 \times 10^4$. Thus, the value of K is 198.

Let $a_n$ be the number of n-bit strings without two consecutive 1s. We can find the first few terms of the sequence to identify the pattern.

• For n=1: The valid strings are "0" and "1". So, $a_1 = 2$.
• For n=2: The valid strings are "00", "01", "10". The string "11" is invalid. So, $a_2 = 3$.
• For n=3: The valid strings are "000", "001", "010", "100", "101". The strings "011", "110", "111" are invalid. So, $a_3 = 5$.

The sequence starts $a_1=2, a_2=3, a_3=5$. Let's check the given options with $n=3$.
Option (b) is $a_n = a_{n-1} + a_{n-2}$.
For $n=3$, this gives $a_3 = a_2 + a_1 = 3 + 2 = 5$. This matches our calculated value.

Let $a_n$ be the number of bit strings of length $n$ that contain two consecutive 1s. We can derive a recurrence relation by considering how such a string can be formed. A valid string of length $n$ can end in 0 or 1.

1. The string ends in 0: The prefix of length $n-1$ must contain '11'. There are $a_{n-1}$ such strings.
2. The string ends in 1:
   • The string ends in '01': The prefix of length $n-2$ must contain '11'. There are $a_{n-2}$ such strings.
   • The string ends in '11': The '11' pattern is satisfied by the last two bits. The prefix of length $n-2$ can be any bit string. There are $2^{n-2}$ such strings.

Since these cases are mutually exclusive, we can sum them to get the total count:
$a_n = a_{n-1} + a_{n-2} + 2^{n-2}$.