Question

Anyone who can give the shortest approach/solution possible will be given a medal. Here's the problem: If a + b = 2^n where n is a real number and f(a) + f(b) = n^2, find f(2002).

Answer 1

What class is this for? Theoretical CS?

Answer 2

First, you should try to find some obvious values for f(x); like
f(1) = 1/2
f(0) = -1/2

Then, you can break the question using any pattern; I am showing one below -
f(2002) + f(46) = 11^2
f(46) + f(18) = 6^2
f(18) + f(14) = 5^2
f(14) + f(2) = 4^2
f(2) + f(0) = 1^2

I think the rest is obvious :)

Answer 3

How did you get \(f(1)=1/2\)?

Answer 4

Plug-in a = b = 1

Answer 5

But if \(a = b = 0\), then \(0 + 0 = 2^{-\infty}\)

Answer 6

But n has to be an integer; so we can put a=b=0.

So, find f(1) first.
Then put a=1 & b=0
:)

Answer 7

Let \(a=b=2\). Then \(2+2=4=2^2\implies n=2\).
\(f(2)+f(2) = 2^2\implies 2f(2) = 4\implies f(2) =2\)

now we say \(0+2=2\implies n=1\)
\(f(0) + f(2) = 1^2\implies f(0)+2=1\implies f(0)=-1\)

Answer 8

Consider any number, \(c=2^m\).
We can say \(c+c=2^m+2^m = 2^{m+1}\implies n=m+1\)
We can say \(f(c)+f(c)=n^2\implies 2f(c) = (m+1)^2\implies f(c) = \frac{(1+m)^2}{2}\)

Answer 9

And that ^^ proves f(x) is not a function in the first place. ;)

Answer 10

Then \(0+c=2^m\implies n=m\)
So \(f(0)+f(c)=n^2\implies f(0) = m^2-\frac{(1+m)^2}{2}\)

We can make \(f(0)\) various values based on what \(c\) we use.

Answer 11

I didn't check for inconsistency..my bad XD

Answer 12

Fibonacci sequence is the same way, unless you add seed data.

Answer 13

The lack of seed data made me suspicious

Answer 14

What is "seed data" ??

Answer 15

for example, f(0) = 0 and f(1) =1 for Fibonacci, or f(0) = 1 and f(1) = 1 for factorial

Answer 16

When you have a recursive function, that is a function defined in terms of itself, then you generally need seed data.

Answer 17

Thanxx :)

Answer 18

But this question looks so open ended that, I'm not sure if it would work even then.

Answer 19

For example, is it true that for any number there is pair of \(a,b\) such that \(a+b=2^n\)?

Answer 20

a unique pair^

Answer 21

Maybe if you just ignore \(f(0)\) and stop at \(f(2)\) it will work?

Answer 22

The problem is that we'll get different values for f(2) also.
For any n; (a,b) is not unique.

Answer 23

I'm not seeing any obvious connection between f(a), f(b), and a + b = 2^n. Are variables "a" and "b" real numbers?

Answer 24

Oh, I just had an insight that variable "n" connects them, perhaps?

Answer 25

wont f(0) = 0, f(1) = 0 work here as initial values ?

0 + 1 = 2^0 ---> n =0
f(0) + f(1) = 0

Answer 26

yes,
a+b = 2^n
=> a = 2^n-b

f(a) + f(b) = n^2
f(2^n-b) + f(b) = n^2

next, look at LastDayWork's first reply

Answer 27

^^ that was for cebroski...

Answer 28

Thanks, @ganeshie8!

Answer 29

np, also u need to figure out below :
2002 = 2^11 - 46

before looking at LastDayWork's work :)

Answer 30

"LastDayWork's work"
XD XD XD

Answer 31

@dumbcow
if \(f(1)=0\) then \(1+1=2^1\implies n=1\)
but \(f(1)+f(1)=0+0 =0^2\implies n=0\)

Answer 32

http://jsfiddle.net/wio_dude/WBpy5/3/

It seems like all initial values are going to be \(c = 2^n\).
In these cases, you would use \(f(c) = (1+n)^2/2\).

There is no value for \(f(0)\).

For cases where \(b \neq 2^n\), then you would find \(n\) such that \(2^{n-1} < b < 2^n\).\[
f(b) = n^2 - f(2^n-b)
\]We know that \(2^n-b<b\), because \[\begin{array}{rcl}
2^{n-1}&<&b\\
2^n &<&2b\\
2^n-b&<&b
\end{array}\]So we know that this recursive function always goes down.

Answer 33

If \(a + b = 2^{n}\)
And \(f(a) + f(b) = n^{2}\)

We have \(f(a) = f(2^{n} - b) = n^{2} - f(b)\)

This recursive definition follows exactly LastDaysWork's example sequence.