Name:      

Directions: Show all work.

1. [6 points] For $n\ge 0$, let

   $$S_n=\sum _{k=1}^{2n}{(-1)}^k{k}^2=-1^2+2^2-3^2+4^2-\cdots -{(2n-1)}^2+{(2n)}^2.$$

   Prove that for each non-negative integer $n$, we have that $S_n=(2n+1)n$.

2. [2 parts, 2 points each] Recall that the adjusted Fibonacci sequence is defined by ${\widehat{F}}_0={\widehat{F}}_1=1$ and ${\widehat{F}}_n={\widehat{F}}_{n-1}+{\widehat{F}}_{n-2}$ for $n\ge 2$.

   1. Let $n$ be a positive integer and let $t$ be the maximum integer such that ${\widehat{F}}_t\le n$. Prove that $n-{\widehat{F}}_t<{\widehat{F}}_{t-1}$. (Hint: there is a short proof, without induction/no minimum counter-example. If stuck, then try a proof by contradiction.)
   2. Prove that each positive integer $n$ is a sum of distinct, non-consecutive adjusted Fibonacci numbers. For example, if $n=20$, then we have $20=13+5+2={\widehat{F}}_6+{\widehat{F}}_4+{\widehat{F}}_2$.