Question

Consider f(0) = 0 and for n \(\ge\) 1, f(n) = f(⌊n/2⌋) + 1. Find a recursion formula for the function.

Answer 1

does "n>1" mean there is no f(1) despite there being an f(0)?

Answer 2

yeah it is kind of confusing
\[f(1)=f(\left \lfloor{\frac{1}{2}}\right \rfloor )+1=f(0)+1=1\] is a start

Answer 3

that is the "floor" or greatest integer function right? \[\left \lfloor{x}\right \rfloor \]

Answer 4

I am sorry for a careless mistake. I've edited the question. \[f(n) =\begin{cases}0 & n = 0\\\left \lfloor{\frac{n}{2}}\right \rfloor +1 & n \ge 1\end{cases}\]
Yes, it is a floor function.

Answer 5

now i am more confused, because now it isn't a recursion

Answer 6

\[f(9)=\lfloor{\frac{9}{2}}\rfloor+1=4+1=5\]

Answer 7

oooh i see
you are supposed to MAKE it a recursion

Answer 8

Oh, yes :|

Answer 9

Question edited, maybe it's clearer now.
Though, in the question, it really says that "Consider the recursion..."

Answer 10

the only thing is see is that \(a_n=a_{n-1}\) for odd \(n\) and \(a_{n-1}+1\) for even \(n\)
there is probably a more sophisticated way to write it

Answer 11

if it really says "consider the recursion..." then something is wrong, because \[f(n) =\begin{cases}0 & n = 0\\\left \lfloor{\frac{n}{2}}\right \rfloor +1 & n \ge 1\end{cases}\] is an explicit formula, not a recursion

Answer 12

nice latex btw

Answer 13

Actually, it's a MC question. But I'd rather know how to do it without any choices given.
Attached is the question. FYI, it is a question from 2011 exam past paper. NOT homework, or current quiz/test/exam.

Thanks to Zarkon :)

Answer 14

*I'd rather like to know how to do

Answer 15

oooh ok ok it is \[f(n) =\begin{cases}0 & n = 0\\f(\left \lfloor{\frac{n}{2}}\right \rfloor) +1 & n \ge 1\end{cases}\]

Answer 16

now it IS a recursion at least

Answer 17

i would start out by computing \(f(1), f(2), f(3), ...\) and see if a pattern emerges

Answer 18

\[f(1)=f(\lfloor{\frac{1}{2}}\rfloor)+1=f(0)+1=1\]

Answer 19

\[f(2)=f(\lfloor{\frac{2}{2}}\rfloor)+1=f(1)+1=1+1=2\]

Answer 20

\[f(3)=f(1)+1=2\\
f(4)=f(2)+1=3\\
f(5)=f(2)+1=3\\
f(6)=f(3)+1=3\] etc

Answer 21

f(7) = f(3) + 1 = 3
So, we get
f(0) = f(0) + 1 = 0 + 1 = 1 [Exceptional case]
f(1) = f(0) + 1 = 0 + 1 = 1 2^0
f(2) = f(1) + 1 = 1 + 1 = 2
f(3) = f(1) + 1 = 1 + 1 = 2 2^1
f(4) = f(2) + 1 = 2 + 1 = 3
f(5) = f(2) + 1 = 2 + 1 = 3
f(6) = f(3) + 1 = 2 + 1 = 3
f(7) = f(3) + 1 = 2 + 1 = 3 2^2
f(8) = f(4) + 1 = 3 + 1 = 4
f(9) = f(4) + 1 = 3 + 1 = 4
f(10) = f(5) + 1 = 3 + 1 = 4
f(11) = f(5) + 1 = 3 + 1 = 4
f(12) = f(6) + 1 = 3 + 1 = 4
f(13) = f(6) + 1 = 3 + 1 = 4
f(14) = f(7) + 1 = 3 + 1 = 4
f(15) = f(7) + 1 = 3 + 1 = 4 2^3


Something to do with 2^n

Answer 22

Oh oh oh!!
remove that exceptional case ... it looks funny!!
f(0) = f(0) + 1 => 0 = 1

Answer 23

LOL without the exceptional case, we don't have f(1)

Answer 24

:S
http://oeis.org/search?q=0%2C1%2C2%2C2%2C3%2C3%2C3%2C3%2C4%2C4%2C4%2C4%2C4%2C4%2C4%2C4&sort=&language=english&go=Search

Answer 25

f(0) = f(0) + 1 = 0 + 1 = 1 [Exceptional case]
f(1) = f(0) + 1 = 0 + 1 = 1 2^0 f(1) = f(0) + 1 = \(\log_2(1)\) + 1 = 1
f(2) = f(1) + 1 = 1 + 1 = 2 f(2) = f(1) + 1 = \(\log_{2}(2)\) + 1 = 2
f(3) = f(1) + 1 = 1 + 1 = 2 2^1 f(3) = f(1) + 1 = \(\lfloor{\log_{2}(3)}\rfloor\) + 1 = 2
f(4) = f(2) + 1 = 2 + 1 = 3 f(4) = f(2) + 1 = \(\log_{2}4\) + 1 = 3
f(5) = f(2) + 1 = 2 + 1 = 3 f(5) = f(2) + 1 = \(\lfloor{\log_{2}(5)}\rfloor\) + 1 = 2
f(6) = f(3) + 1 = 2 + 1 = 3 f(6) = f(3) + 1 = \(\lfloor{\log_{2}(6)}\rfloor\) + 1 = 3
f(7) = f(3) + 1 = 2 + 1 = 3 2^2 f(7) = f(3) + 1 = \(\lfloor{\log_{2}(7)}\rfloor\) + 1 = 3
f(8) = f(4) + 1 = 3 + 1 = 4 f(8) = f(4) + 1 = \(\log_2{8}\)+ 1 = 3
f(9) = f(4) + 1 = 3 + 1 = 4 f(9) = f(4) + 1 = \(\lfloor{\log_{2}(9)}\rfloor\) + 1 = 4
f(10) = f(5) + 1 = 3 + 1 = 4 f(10) = f(5) + 1 = \(\lfloor{\log_{2}(10)}\rfloor\) + 1 = 4
f(11) = f(5) + 1 = 3 + 1 = 4 f(11) = f(5) + 1 = \(\lfloor{\log_{2}(11)}\rfloor\) + 1 = 4
f(12) = f(6) + 1 = 3 + 1 = 4 f(12) = f(6) + 1 = \(\lfloor{\log_{2}(12)}\rfloor\) + 1 = 4
f(13) = f(6) + 1 = 3 + 1 = 4 f(13) = f(6) + 1 = \(\lfloor{\log_{2}(13)}\rfloor\) + 1 = 4
f(14) = f(7) + 1 = 3 + 1 = 4 f(14) = f(7) + 1 = \(\lfloor{\log_{2}(14)}\rfloor\) + 1 = 4
f(15) = f(7) + 1 = 3 + 1 = 4 2^3 f(15) = f(7) + 1 = \(\lfloor{\log_{2}(15)}\rfloor\) + 1 = 4

Answer 26

http://assets.openstudy.com/updates/attachments/52ab1deae4b0a4b4fc265de8-experimentx-1386949672651-screenshotfrom20131213212658.png

Answer 27

So, we get \(f(n) = \lfloor{\log_{2}(n)}\rfloor + 1 \), which is the same as \(f(n) = \lfloor{\log_{2}(n) + 1}\rfloor \)

Answer 28

for \(n \ge 1\)

Answer 29

@experimentX what software is that?

Answer 30

Pro LaTeX xD (jkjk not pro at all)
\[\begin{array}{r|c|l}
f(0)=f(0)+1=0+1=1 & & \mbox{[Exceptional case]}\\\hline
f(1)=f(0)+1=0+1=1 & 2^0 & f(1)=f(0)+1=\log_21+1=1\\\hline
f(2)=f(1)+1=1+1=2 & & f(2)=f(1)+1=\log_22+1=2\\\hline
f(3)=f(1)+1=1+1=2 & 2^1 & f(3)=f(1)+1=\left\lfloor\log_23\right\rfloor+1=2\\\hline
f(4)=f(2)+1=2+1=3 & & f(4)=f(2)+1=\log_24+1=3\\\hline
f(5)=f(2)+1=2+1=3 & & f(5)=f(2)+1=\left\lfloor\log_25\right\rfloor+1=3\\\hline
f(6)=f(3)+1=2+1=3 & & f(6)=f(3)+1=\left\lfloor\log_26\right\rfloor+1=3\\\hline
f(7)=f(3)+1=2+1=3 & 2^2 & f(7)=f(3)+1=\left\lfloor\log_27\right\rfloor+1=3\\\hline
f(8)=f(4)+1=3+1=4 & & f(8)=f(4)+1=\log_28+1=3\\\hline
f(9)=f(4)+1=3+1=4 & & f(9)=f(4)+1=\left\lfloor\log_29\right\rfloor+1=4\\\hline
f(10)=f(5)+1=3+1=4 & & f(10)=f(5)+1=\left\lfloor\log_210\right\rfloor+1=4\\\hline
f(11)=f(5)+1=3+1=4 & & f(11)=f(5)+1=\left\lfloor\log_211\right\rfloor+1=4\\\hline
f(12)=f(6)+1=3+1=4 & & f(12)=f(6)+1=\left\lfloor\log_212\right\rfloor+1=4\\\hline
f(13)=f(6)+1=3+1=4 & & f(13)=f(6)+1=\left\lfloor\log_213\right\rfloor+1=4\\\hline
f(14)=f(7)+1=3+1=4 & & f(14)=f(7)+1=\left\lfloor\log_214\right\rfloor+1=4\\\hline
f(15)=f(7)+1=3+1=4 & 2^3 & f(15)=f(7)+1=\left\lfloor\log_215\right\rfloor+1=4\\
\end{array}\]

Answer 31

How are we getting f(odd/2), especially f(1/2)?

Answer 32

f(1/2) means n = 1/2
(1/2)/2 = 0.25
Floor of (1/2)/2 is 0
So, f(1/2) = 0+1 = 1

Answer 33

Oh my poor spinning head! I am so impressed with all this math flowing around. (-:

Answer 34

thats a lotta latex

Answer 35

lolz

Answer 36

@kc_kennylau that's Mathematica in ubuntu. Check this thread.
http://math.stackexchange.com/questions/605751/finding-function-such-that-f2x-fx-1

Answer 37

\[ f(2^k) = k + 1\]
Let \( 2^{k-1}\le x < 2^k \) using \( f(n) = f(\lfloor n/2 \rfloor ) + 1 \) gives \( f(2^{k-1}) = f(x) = f(2^k) - 1\)
which gives \( f(n) = \lfloor \log_2 n + 1 \rfloor \)