LaTeX Writing Sample

Please determine a closed formula for the number \(S_n\) of subsets of \([n]\) that have no consecutive elements, if the elements of \([n]\) are thought of as positive integers with the usual order relation.

Claim the closed form for \( S_n \) is \[ S(n) = \frac{5 + 3 \sqrt{5}}{10} \cdot \left( \frac{1 + \sqrt{5}}{2} \right)^n + \frac{5 - 3 \sqrt{5}}{10} \cdot \left( \frac{1 - \sqrt{5}}{2} \right)^n \]

Proof

Consider the following sets of solutions \begin{equation} \begin{split} S_0 &= \{ \varnothing \} \\ S_1 &= \{ \varnothing \} , \{ 1 \} \\ S_2 &= \{ \varnothing \} , \{ 1 \} , \{ 2 \} \\ S_3 &= \{ \varnothing \} , \{ 1 \} , \{ 2 \} , \{ 3 \} , \{ 1, 3 \} \end{split} \end{equation}

Note that \( S_2 \) can be rewritten to be \( S_2 = S_1 + \{ 2 \} \) where \( \{ 2 \} \) is what results from stuffing 2 into the null set.

Similarly, \( S_3 \) is also equal to \( S_2 + \{ 3 \} , \{ 1, 3 \} \) where \( \{ 3 \} , \{ 1, 3 \} \) is what you get from stuffing 3 to each solution in \( S_1 \).

Without loss of generality, this argument applies to each solution in \( S_n \) resulting in the recursive equation \begin{equation} S_n = S_{n-1} + S_{n-2} \text{ where } n \geq 2 \text{ and } S_0 = 1, S_1 = 2 \end{equation}

As this is clearly the same form as the Fibonacci equation we know too that \begin{equation} S(n) = A \left( \frac{1 + \sqrt{5}}{2} \right)^n + B \left( \frac{1 - \sqrt{5}}{2} \right)^n \end{equation} and solving this equation for \( S(0) \) gives us that \( A = 1 - B \) which allows for the simplification of the equation into one with a single variable and so we can then solve \( S(1) \) for \( B \) which yields that \( B = \frac{5 - 3 \sqrt{5}}{10} \) and therefore we also know that \( A = \frac{5 + 3 \sqrt{5}}{10} \).

Putting in the answers for \( A \) and \( B \) into the equation for \( S(n) \) yields our original equation. \( \blacksquare \)

Suppose \(x\) is a positive integer with \(n\) digits, say \(x = d_1 d_2 d_3 \cdots d_n \). In other words, \( d_i \in \{0,1,2,\dots, 9\}\) for \( 1 \leq i \leq n \), but \( d_1 \neq 0 \). Please prove that if \(9\) is a divisor of \( d_1 + d_2 + \cdots + d_n \), then \(9\) is a divisor of \( x \). Recall that, for \( a, b \in \mathbb{Z} \), \(a\) is a divisor of \( b \) if \( b = ak \), for some \( k \in \mathbb{Z} \).

First, some notation. Let \( 9^{[n]} \) be a number that consists of \( n \) sequential nines. Thus \( 9^{[3]} = 999 \).

Lemma: \( 10^{n} = 9^{[n-1]} + 1 \) thus \[ 10^{3} = 9^{[3-1]} + 1 = 9^{[2]} + 1 = 99 + 1 = 100 \]

1. Proof of Lemma: In base 10, all numbers can be expressed as \begin{equation} d_1 \cdot 10^{n} + d_2 \cdot 10^{n-1} + \cdots + d_{n-1} \cdot 10^{1} + d_n \cdot 10^{0} \end{equation}
2. Consider that \( 9 + 1 = 10 \) can be rewritten as \( 9 \cdot 10^{0} + 1 \cdot 10^{0} \) and that \( 10 = 1 \cdot 10^{1} \).
3. Thus, \begin{equation} 9 \cdot 10^{0} + 1 \cdot 10^{0} = 10 \cdot 10^{0} = 1 \cdot 10^{1} \end{equation} and so \begin{equation} \begin{split} 9 \cdot 10^{n-1} + 9 \cdot 10^{n-2} + \cdots + 9 \cdot 10^{1} + 9 \cdot 10^{0} + 1 \cdot 10^{0} &=\\ 9 \cdot 10^{n-1} + 9 \cdot 10^{n-2} + \cdots + 9 \cdot 10^{1} + 10 \cdot 10^{0} &=\\ 9 \cdot 10^{n-1} + 9 \cdot 10^{n-2} + \cdots + 9 \cdot 10^{1} + 1 \cdot 10^{1} &=\\ 9 \cdot 10^{n-1} + 9 \cdot 10^{n-2} + \cdots + 10 \cdot 10^{1} &=\\ 9 \cdot 10^{n-1} + 9 \cdot 10^{n-2} + 1 \cdot 10^{n-2} &=\\ 9 \cdot 10^{n-1} + 10 \cdot 10^{n-2} &=\\ 9 \cdot 10^{n-1} + 1 \cdot 10^{n-1}&= \\ 10 \cdot 10^{n-1} &=\\ 10^{n} \end{split} \end{equation}
4. It should be clear that \( 9^{[n]} = 9 \cdot 1^{[n]} \) and thus that \( 9 \) is a divisor of \( 9^{[n]} \).

Consider the digit expansion shown in our lemma. Using that lemma, the expansion can be rewritten as \begin{equation} \begin{split} d_1 \cdot 10^{n} + d_2 \cdot 10^{n-1} + \cdots + d_{n-1} \cdot 10^{1} + d_n \cdot 10^{0} &= \\ d_1 \cdot \left( 9^{[n-1]} + 1 \right) + d_2 \cdot \left( 9^{[n-2]} + 1 \right) + \cdots + d_n \cdot \left( 9^{[0]} + 1 \right) \end{split} \end{equation} Distributing and combining like terms yields \begin{equation} d_1 + d_2 + \cdots + d_n + d_1 \cdot 9^{[n-1]} + d_2 \cdot 9^{[n-2]} + \cdots + d_n \cdot 9^{[0]} \end{equation}

As addition is closed under \( \mathbb{Z} \), \( d_1 + d_2 + \cdots + d_n = S \) where \( S \in \mathbb{Z} \).

For every element that remains, we know that \(9\) is a divisor of each element and so if \(9\) is also a divisor of \( S \) then \(9\) is a divisor of \(x\). As this is what we are assuming, we know that, when the digits of a number sum to a number that is a divisor of \(9\) then the we know too that \(9\) is a divisor of that number. \( \blacksquare \)