LaTeX Writing Sample

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

Claim the closed form for $S_n$ is $$S\left(n\right)=\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{array}{cc}{S}_0& =\left\{\varnothing \right\}\\ S_1& =\left\{\varnothing \right\},\left\{1\right\}\\ S_2& =\left\{\varnothing \right\},\left\{1\right\},\left\{2\right\}\\ S_3& =\left\{\varnothing \right\},\left\{1\right\},\left\{2\right\},\left\{3\right\},\{1,3\}\end{array}$$

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

Similarly, $S_3$ is also equal to $S_2+\left\{3\right\},\{1,3\}$ where $\left\{3\right\},\{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 $$S_n=S_{n-1}+S_{n-2}\text{where}n\ge 2\text{and}{S}_0=1,S_1=2$$

As this is clearly the same form as the Fibonacci equation we know too that $$S\left(n\right)=A{\left(\frac{1+\sqrt{5}}{2}\right)}^n+B{\left(\frac{1-\sqrt{5}}{2}\right)}^n$$ and solving this equation for $S\left(0\right)$ 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\left(1\right)$ 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\left(n\right)$ yields our original equation. $■$

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\le i\le n$, but $d_1\ne 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 Z$, $a$ is a divisor of $b$ if $b=ak$, for some $k\in Z$.

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

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

1. Proof of Lemma: In base 10, all numbers can be expressed as $$d_1\cdot {10}^n+d_2\cdot {10}^{n-1}+\cdots +d_{n-1}\cdot {10}^1+d_n\cdot {10}^0$$
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, $$9\cdot {10}^0+1\cdot {10}^0=10\cdot {10}^0=1\cdot {10}^1$$ and so $$\begin{array}{cc}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{array}$$
4. It should be clear that $9^{\left[n\right]}=9\cdot 1^{\left[n\right]}$ and thus that $9$ is a divisor of $9^{\left[n\right]}$.

Consider the digit expansion shown in our lemma. Using that lemma, the expansion can be rewritten as $$\begin{array}{cc}{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 (9^{[n-1]}+1)+d_2\cdot (9^{[n-2]}+1)+\cdots +d_n\cdot (9^{\left[0\right]}+1)& \end{array}$$ Distributing and combining like terms yields $$d_1+d_2+\cdots +d_n+d_1\cdot 9^{[n-1]}+d_2\cdot 9^{[n-2]}+\cdots +d_n\cdot 9^{\left[0\right]}$$

As addition is closed under $Z$, $d_1+d_2+\cdots +d_n=S$ where $S\in 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. $■$