LaTeX Writing Sample

Please determine a closed formula for the number Sn 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 Sn is S(n)=5+3√510⋅(1+√52)n+5−3√510⋅(1−√52)n

Proof

Consider the following sets of solutions S0={∅}S1={∅},{1}S2={∅},{1},{2}S3={∅},{1},{2},{3},{1,3}

Note that S2 can be rewritten to be S2=S1+{2} where {2} is what results from stuffing 2 into the null set.

Similarly, S3 is also equal to S2+{3},{1,3} where {3},{1,3} is what you get from stuffing 3 to each solution in S1.

Without loss of generality, this argument applies to each solution in Sn resulting in the recursive equation Sn=Sn−1+Sn−2 where n≥2 and S0=1,S1=2

As this is clearly the same form as the Fibonacci equation we know too that S(n)=A(1+√52)n+B(1−√52)n 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=5−3√510 and therefore we also know that A=5+3√510.

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

Suppose x is a positive integer with n digits, say x=d1d2d3⋯dn. In other words, di∈{0,1,2,…,9} for 1≤i≤n, but d1≠0. Please prove that if 9 is a divisor of d1+d2+⋯+dn, then 9 is a divisor of x. Recall that, for a,b∈Z, a is a divisor of b if b=ak, for some k∈Z.

First, some notation. Let 9[n] be a number that consists of n sequential nines. Thus 9[3]=999.

Lemma: 10n=9[n−1]+1 thus 103=9[3−1]+1=9[2]+1=99+1=100

1. Proof of Lemma: In base 10, all numbers can be expressed as d1⋅10n+d2⋅10n−1+⋯+dn−1⋅101+dn⋅100
2. Consider that 9+1=10 can be rewritten as 9⋅100+1⋅100 and that 10=1⋅101.
3. Thus, 9⋅100+1⋅100=10⋅100=1⋅101 and so 9⋅10n−1+9⋅10n−2+⋯+9⋅101+9⋅100+1⋅100=9⋅10n−1+9⋅10n−2+⋯+9⋅101+10⋅100=9⋅10n−1+9⋅10n−2+⋯+9⋅101+1⋅101=9⋅10n−1+9⋅10n−2+⋯+10⋅101=9⋅10n−1+9⋅10n−2+1⋅10n−2=9⋅10n−1+10⋅10n−2=9⋅10n−1+1⋅10n−1=10⋅10n−1=10n
4. It should be clear that 9[n]=9⋅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 d1⋅10n+d2⋅10n−1+⋯+dn−1⋅101+dn⋅100=d1⋅(9[n−1]+1)+d2⋅(9[n−2]+1)+⋯+dn⋅(9[0]+1) Distributing and combining like terms yields d1+d2+⋯+dn+d1⋅9[n−1]+d2⋅9[n−2]+⋯+dn⋅9[0]

As addition is closed under Z, d1+d2+⋯+dn=S where S∈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. ◼