f(3x) = x + f(3x-3)
f(3) =1

Find f(999)

Question

f(3x) = x + f(3x-3) 
f(3) =1 

Find f(999)

domebotnos · Answer

f is 999??

domebotnos · Answer

oh wouldnt f be 1??

rational · Answer

f is a function here..

domebotnos · Answer

$$f(3x)=x =+ (3x-3)$$

parthkohli · Answer

$$f(k) - f(k - 3) = k/3$$I'm sensing some telescoping here.

rational · Answer

I think that looks like a 3 level recurrence relation
$$a_n -a_{n-3} = n/3,~~a_3 = 1$$

impossible to have an unique solution without knowing $a_1$ and $a_2$

parthkohli · Answer

Or, rather,$$f(k+3) - f(k) = k/3 + 1$$So$$f(6) = 5$$$$f(9) = 8$$$$f(12) = 13$$FIBONACCI!

parthkohli · Answer

$$f(15) = 6 + 13 = 19$$nvm

anonymous · Answer

is it 333*167 -1 ?

parthkohli · Answer

So hold on, it's possible to do this by telescoping, yes?

anonymous · Answer

For $x=1$ we get another initial point,
$$f(3)=1+f(0)~~\implies~~f(0)=0$$
How many more are needed to solve the recurrence @rational?

rational · Answer

that looks very huge but it seems you both are on right tack..

parthkohli · Answer

$$f(3x + 3) - f(3x) = x+1$$$$f(6) - f(3) = 2$$$$f(9) - f(6) = 3$$$$f(12) - f(9) = 4$$yup

rational · Answer

hey @divu.mkr  sry your answer is correct!

parthkohli · Answer

$$\vdots \ f(999) - f(996) = 334$$

anonymous · Answer

f(3x) = x+ f(3(x-1)) = x+ x-1 f(3(x-2)) = x+x-1 +x-2 .... +2 + f(3) = x+x-1 + x-2 .... +2 +1 
x(x+1)/2

parthkohli · Answer

Add all of them and$$f(3) + f(999) = \frac{333\cdot 334}{2}$$$$f(999) = 333\cdot 167 - 1$$

parthkohli · Answer

Hold on. It should be -2.

parthkohli · Answer

Because 1 is not included in the sum. It starts from 2.

anonymous · Answer

isnt it f(999) - f(3) ?

parthkohli · Answer

Oh, that's right.

parthkohli · Answer

Which means that there's no -1 in there?

rational · Answer

Yes both solutions are correct!

Looks the sequence formed by picking third terms gives sum of first "x/3" natural numbers

anonymous · Answer

yep @ParthKohli

parthkohli · Answer

@rational which is why there can't be any -1, ahhhhh.

rational · Answer

f(3x) = x(x+1)/2

looks good to me
plugin x=333 to get f(3*333) = 55611

gotcha!

parthkohli · Answer

That was simple. I wonder why we couldn't notice that in the recurrence relation itself. >_<

kainui · Answer

I found an alternate way to the recurrence relation that's kinda cute. Let's make a new function g(x)=3x and then we can make another new function h(x)=f(g(x)). Then we can transform our condition f(3)=1 into f(g(1))=h(1)=1 and the thing to find f(g(333))=h(333). Our equation then becomes $$\Large h(x)=x+h(x-1)$$ substituting in x+1 we get $$\Large h(x+1)=x+1+h(x)$$ and the rest is just the same technique as you would guess it to be.

rational · Answer

Thats same as divu.mkr's solution except it looks more neat :)