can someone help me
- Thread starter chad brad
- Start date
Dr.Peterson
Elite Member
- Joined
- Nov 12, 2017
- Messages
- 16,087
You must have made a mistake.
What did you get for f(1), f(2), f(4), f(8), f(16), and f(32)? Did you see any pattern that might lead to a general formula?
What did you get for each of the options for n = 1, 2, 4, 8, 16, 32?
It is impossible to see where you have gone astray, if you have gone astray, because you show no work.
Actually, all of the proposed answers work if k = 0.
[MATH]k \in \mathbb Z^+ \implies n = 2^k > 1 \text { and } \dfrac{n}{2} \in \mathbb Z \implies [/MATH]
[MATH]\left \lfloor \dfrac{n}{2} \right \rfloor = \dfrac{n}{2} \implies f(n) = 2 * f\left(\dfrac{n}{2}\right) + 1 = n + 1.[/MATH] ...................[edited]
So you are correct. The answers do not work.
In fact for any even integer x, the result will be x + 1.
Actually, all of the proposed answers work if k = 0.
[MATH]k \in \mathbb Z^+ \implies n = 2^k > 1 \text { and } \dfrac{n}{2} \in \mathbb Z \implies [/MATH]
[MATH]\left \lfloor \dfrac{n}{2} \right \rfloor = \dfrac{n}{2} \implies f(n) = 2 * f\left(\dfrac{n}{2}\right) + 1 = n + 1.[/MATH] ...................[edited]
So you are correct. The answers do not work.
In fact for any even integer x, the result will be x + 1.
HallsofIvy
Elite Member
- Joined
- Jan 27, 2012
- Messages
- 7,763
The crucial point is that \(\displaystyle 2^k\), as you repeatedly divide by 2, is always an integer (so you don't have to worry about the "integer" part) and always a power of two.
For example if k= 4 (and \(\displaystyle x= 2^4= 16\)) then f(x)= 2f(8)+ 1. But f(8)= 2f(4)+ 1, f(4)= 2f(2)+ 1, f(2)= 2f(1)+ 1, and f(1)= 0. So f(2)= 2(0)+ 1= 1, f(4)= 2(1)+ 1= 3, f(8)= 2(3)+ 1= 7, and f(16)= 2(7)+ 1= 15.
Hey, that's just \(\displaystyle x-1\)! I could try to prove that works for all x BUT I see that n-1 is one of the answers and none of the other answers are 15 for n= 16. Ah, the joys of "multiple guess" questions!
For example if k= 4 (and \(\displaystyle x= 2^4= 16\)) then f(x)= 2f(8)+ 1. But f(8)= 2f(4)+ 1, f(4)= 2f(2)+ 1, f(2)= 2f(1)+ 1, and f(1)= 0. So f(2)= 2(0)+ 1= 1, f(4)= 2(1)+ 1= 3, f(8)= 2(3)+ 1= 7, and f(16)= 2(7)+ 1= 15.
Hey, that's just \(\displaystyle x-1\)! I could try to prove that works for all x BUT I see that n-1 is one of the answers and none of the other answers are 15 for n= 16. Ah, the joys of "multiple guess" questions!