Numbers expressible as $\sum_{i=1}^{n}(-1)^{a_{i}}2^{b_{i}}$

For discussing Olympiad Level Number Theory problems
rah4927
Posts:110
Joined:Sat Feb 07, 2015 9:47 pm
Numbers expressible as $\sum_{i=1}^{n}(-1)^{a_{i}}2^{b_{i}}$

Unread post by rah4927 » Sun Feb 19, 2017 11:15 am

Let $n$ be a positive integer. Find, with proof, the least positive integer $d_{n}$ which cannot be expressed in the form \[\sum_{i=1}^{n}(-1)^{a_{i}}2^{b_{i}},\]
where $a_{i}$ and $b_{i}$ are nonnegative integers for each $i.$

User avatar
Mallika Prova
Posts:6
Joined:Thu Dec 05, 2013 7:44 pm
Location:Mymensingh,Bangladesh

Re: Numbers expressible as $\sum_{i=1}^{n}(-1)^{a_{i}}2^{b_{

Unread post by Mallika Prova » Thu Apr 13, 2017 1:20 pm

$d_n$ the binary representation of a number that can't be expressed with a subtraction of two $n$ bit strings

having a total of $n$ $1's$ together.

we will prove that for a $d_n < 2^n $ there exists such $n$ bit strings

for a number $x < 2^n$ is a $n$ bit string with atmost $n$ $1's$

now for $a_0$ adjacent $0's$ we can find $\underbrace{10101010...1010}_{a_0}$ and $\underbrace{10101010...1010}_{a_0}$

and for $a_1$ adjacent $1's$ we can find $\underbrace{11111111...1111}_{a_1}$ and $\underbrace{00000000...0000}_{a_1}$


and we are done.. having $d_n=2^n$ a binary string with $1$ $1's$ and $n$ $0's$
If you do what interests you , atleast one person is pleased.

Post Reply