Prove-that-n-1-2-n-2-4-n-4-8-n-8-16-n-Such-that-denotes-greatest-integer-function-and-n-N-

Question Number 7317 by lakshaysethi last updated on 24/Aug/16

P r o v e t h a t [\frac{n + 1}{2}] + [\frac{n + 2}{4}] + [\frac{n + 4}{8}] + [\frac{n + 8}{16}] + \dots \dots . . = n .

S u c h t h a t [.] d e n o t e s g r e a t e s t i n t e g e r f u n c t i o n a n d n \in N .

Commented by FilupSmith last updated on 23/Aug/16

S = \underset{t = 1}{\sum^{\infty}} ⌈ \frac{n + 2^{t - 1}}{2^{t}} ⌉

S = \underset{t = 1}{\sum^{\infty}} ⌈ \frac{n}{2^{t}} + \frac{1}{2} ⌉

if n ⩾ 2^{t} \Rightarrow \frac{n}{2^{t}} ⩾ 1

∴ ⌈ \frac{n}{2^{t}} + \frac{1}{2} ⌉ ⩾ 2

if n ⩽ 2^{t} \Rightarrow \frac{n}{2^{t}} ⩽ 1

∴ ⌈ \frac{n}{2^{t}} + \frac{1}{2} ⌉ = 1 \lor 2

∴ sequence is :

2 + 2 + \dots + 1 + 1 + 1 + \dots + 0 (0 w h e n t = \infty)

∴ S = \infty

∴ ⌈ \frac{n + 2}{4} ⌉ + ⌈ \frac{n + 4}{6} ⌉ + ⌈ \frac{n + 8}{16} ⌉ + \dots = n is false

this is because for \frac{n + 2^{t}}{2^{t + 1}} > 1, ⌈ \frac{n + 2^{t}}{2^{t + 1}} ⌉ ⩾ 1

t h e r e f o r e n o s o l u t i o n e x i s t s f o r n \in N

Commented by prakash jain last updated on 23/Aug/16

Filup, n = 1, 2, 3, 4, 5 e t c satisfy this equation

n = 1, 1 + 0 + 0 . . = 1 = n

n = 2, 1 + 1 + 0 + 0 + . . = 2 = n

n = 3, 2 + 1 + 0 + 0 . . = 3 = n

n = 4, 2 + 1 + 1 + . . = 4 = n

n = 5 : 3 + 1 + 1 = 5 = n

n = 6 : 3 + 2 + 1 + . . = n

Lakshay, is the question asking for proof ?

Commented by Yozzia last updated on 24/Aug/16

[\frac{n}{2} + \frac{1}{2}] + [\frac{n}{4} + \frac{1}{2}] + [\frac{n}{8} + \frac{1}{2}] + [\frac{n}{16} + \frac{1}{2}] + \dots + [\frac{n}{2^{k}} + \frac{1}{2}] = S_{k}

A n y i n t e g e r c a n b e r e p r e s e n t e d i n

b a s e 2 a c c o r d i n g t o t h e b a s e r e p r e s e n t a t i o n t h e o r e m .

∴ n = \underset{i = 0}{\sum^{m}} a_{i} 2^{i} w h e r e e a c h a_{i} = 0 \lor 1 .

∴ \frac{n}{2^{k}} + \frac{1}{2} = \frac{1}{2} + \underset{i = 0}{\sum^{m}} a_{i} 2^{i - k} .

N o w, f o r k, m \in N, k < m o r k = m o r k > m .

I f k < m t h e n f o r s o m e i \in Z^{⩾}, i - k < 0

o r i < k \Rightarrow i ⩽ k - 1 . H e n c e w e c a n w r i t e

\frac{n}{2^{k}} + \frac{1}{2} = R + a_{k} 2^{k - k} + a_{k + 1} 2^{(k + 1) - k} + a_{k + 2} 2^{(k + 2) - k} + \dots + a_{m - 1} 2^{(m - 1) - k} + a_{m} 2^{m - k}

\frac{n}{2^{k}} + \frac{1}{2} = R + a_{k} + a_{k + 1} 2 + a_{k + 2} 2^{2} + \dots + a_{m - 1} 2^{(m - 1) - k} + a_{m} 2^{m - k}

w h e r e R = 2^{- 1} + a_{0} 2^{0 - k} + a_{1} 2^{1 - k} + a_{2} 2^{2 - k} + a_{3} 2^{3 - k} + \dots + a_{k - 2} 2^{(k - 2) - k} + a_{k - 1} 2^{(k - 1) - k} .

I t i s c l e a r t h a t t h e f r a c t i o n a l p a r t o f \frac{n}{2^{k}} + \frac{1}{2}

c a n o n l y c o m e f r o m t h e R t e r m .

R = 2^{- 1} + a_{k - 1} 2^{- 1} + a_{k - 2} 2^{- 2} + \dots + a_{3} 2^{3 - k} + a_{2} 2^{2 - k} + a_{1} 2^{1 - k} + a_{0} 2^{- k}

W e k n o w t h a t m a x (a_{i}) = 1 a n d m i n (a_{i}) = 0 .

∴ 2^{- 1} + 0 + 0 + 0 + \dots + 0 ⩽ R ⩽ 2^{- 1} + 2^{- 1} + 2^{- 2} + \dots + 2^{3 - k} + 2^{2 - k} + 2^{1 - k} + 2^{- k}

\frac{1}{2} ⩽ R ⩽ \frac{1}{2} + \frac{\frac{1}{2} ({(\frac{1}{2})}^{k + 1} - 1)}{\frac{1}{2} - 1}

\frac{1}{2} ⩽ R ⩽ \frac{3}{2} - \frac{1}{2^{k + 1}} f o r a l l k \in N .

S i n c e k ⩾ 1 \Rightarrow m i n (\frac{3}{2} - \frac{1}{2^{k + 1}}) = \frac{6}{4} - \frac{1}{4} = \frac{5}{4} > 1

∴ \frac{1}{2} ⩽ R ⩽ \frac{5}{4} < \frac{3}{2}

\Rightarrow ⌊ R ⌋ = 0 o r ⌊ R ⌋ = 1

I f \frac{1}{2} ⩽ R < 1 \Rightarrow ⌊ R ⌋ = 0 \Rightarrow ⌊ \frac{n}{2^{k}} + \frac{1}{2} ⌋ = a_{k} + a_{k + 1} 2 + a_{k + 2} 2^{2} + a_{k + 3} 2^{3} + \dots + a_{m} 2^{m - k} = u (k) .

∴ S_{k} = \underset{i = 1}{\sum^{k}} u (i)

S_{k} = \frac{1}{2} {2 a_{1} + 2^{2} a_{2} + 2^{3} a_{3} + 2^{4} a_{4} + \dots + a_{m} 2^{m}}

+ \frac{1}{2^{2}} {a_{2} 2^{2} + 2^{3} a_{3} + 2^{4} a_{4} + 2^{5} a_{5} + \dots + a_{m} 2^{m}}

+ \frac{1}{2^{3}} {a_{3} 2^{3} + 2^{4} a_{4} + 2^{5} a_{5} + 2^{6} a_{6} + \dots + a_{m} 2^{m}}

+ \dots + \frac{1}{2^{k}} {a_{k} 2^{k} + a_{k + 1} 2^{k + 1} + a_{k + 2} 2^{k + 2} + \dots + a_{m} 2^{m}}

S_{k} = \frac{1}{2} (n - a_{0}) + \frac{1}{2^{2}} (n - a_{0} - 2 a_{1}) + \frac{1}{2^{3}} (n - a_{0} - 2 a_{1} - 2^{2} a_{2})

+ \dots + \frac{1}{2^{k}} (n - \underset{i = 0}{\sum^{k - 1}} a_{i} 2^{i})

S_{k} = n \frac{\frac{1}{2} (1 - \frac{1}{2^{k + 1}})}{1 - \frac{1}{2}} - \underset{j = 1}{\sum^{k}} {\frac{1}{2^{j}} \underset{i = 0}{\sum^{j - 1}} a_{i} 2^{i}}

S_{k} = n - [\frac{n}{2^{k + 1}} + \underset{j = 0}{\sum^{k}} {\frac{1}{2^{j}} \underset{i = 0}{\sum^{j - 1}} a_{i} 2^{i}}]

- - - - - - - - - - - - - - - - - - - - - - - - -

I f k = m \Rightarrow \frac{n}{2^{m}} + \frac{1}{2} = R

w h e r e R = 2^{- 1} + a_{0} 2^{- m} + a_{1} 2^{1 - m} + a_{2} 2^{2 - m} + a_{3} 2^{3 - m} + \dots + a_{m - 2} 2^{m - 2 - m} + a_{m - 1} 2^{m - 1 - m} + a_{m} 2^{m - m}

R = 2^{- 1} + a_{m} + a_{m - 1} \frac{1}{2} + a_{m - 2} \frac{1}{2^{2}} + \dots + a_{3} \frac{1}{2^{m - 3}} + a_{2} \frac{1}{2^{m - 2}} + a_{1} \frac{1}{2^{m - 1}} + a_{0} \frac{1}{2^{m}} .

2^{- 1} ⩽ R ⩽ \frac{3}{2} + \frac{\frac{1}{2} (1 - \frac{1}{2^{m + 1}})}{1 - \frac{1}{2}}

2^{- 1} ⩽ R ⩽ \frac{5}{2} - \frac{1}{2^{m + 1}}

\Rightarrow ⌊ R ⌋ = 0, 1, 2

- - - - - - - - - - - - - - - - - - - - - - -

C o n t i n u e \dots

Commented by lakshaysethi last updated on 24/Aug/16

y e s s i r (t o p r a k a s h j a i n s i r)