I need to prove that any integer can created using a sum of elements in $a_{n}=2a_{n-1}-\left\lfloor \frac{a_{n-1}}{2}\right\rfloor ,a_{1}=1$ without repetition.
My attempt was just bad...
I've tried proving by induction but it I'm not sure it's legitimate.
I've divided the proof into 2 cases:
- $k=1$ then it's obvious since $a_1 =1 $
-$k\geq2$ by induction let's prove that any $k\geq2\in\mathbb{N}$ can be created using the above mentioned series without using $a_1$. For $k=2$ it works since $a_2=2$ and given it's correct for some $k$, for $k+1$ we use the I.H for $k$ and then use $a_1=1$ since we did not use it. It's bad...
I've also tried looking at $a_{n+1}-a_n$ but it didn't help.
Two main questions:
- Any clues to how would I prove it?
- I've tried to understand how to find a general non-recursive formula for this series and couldn't( since it's not linear and not anything I've learned so far...). This part is actually pure curiosity and is not homework but it really is more interesting :)
Answer
It is more natural to use induction on $a_n$. Let the inductive hypothesis be that it is possible to represent the numbers $1\ldots\ a_n$ using $a_1 \ldots\ a_n$. This is obviously true for $n = 1$; assume it is also true for $n = k$. Then, take some $1 \leq\ x \leq\ a_{k+1}$. If $1 \leq\ x \leq\ a_k$ then $x$ has a representation by the inductive hypothesis and if $x = a_{k+1}$ then $x$ can obviously be represented. Otherwise, we will represent $x$ as $a_{k} + (x - a_{k})$. To ensure that it is valid to do this, we need only verify that $1 \leq\ x - a_{k} \lt\ a_{k}$. Note that the right bound is strict in order to enforce uniqueness. Taking $a_{k} \lt\ x \lt\ a_{k+1}$, we have
$a_{k} \lt\ x \lt\ 2a_{k}-\lfloor \frac{a_k}{2} \rfloor$
$0 \lt\ x - a_k \lt\ a_{k}-\lfloor \frac{a_k}{2}\rfloor \lt a_k$ (if $k > 1$)
$1 \leq\ x - a_k \lt a_k$
The result we wanted to show. Hence, any number can be so represented.
No comments:
Post a Comment