Question

Some recurrence relation functional equation thing

Answer 1

I'm gonna define the operator \(\Delta\) as:
\[\Delta f(x) = \frac{f(x+h)-f(x)}{h}\]

You can apply it multiple times, so doing it 2 times looks like this: \(\Delta^2 f(x)\).

Find as many solutions as you can to:

\[\Delta^k f(x) = f(x)\]

with the condition that for \(n < k\)

\[\Delta^n f(x) \ne f(x)\]

Good luck girls and boys! ;P

Answer 2

\[\Delta f(x)=\frac{f(x+h)-f(x)}{h}=g_0(x) \\ \Delta ^2 f(x)=\frac{g_0(x+h)-g_0(x)}{h}=\frac{\frac{f([x+h]+h)-f(x+h)}{h}-\frac{f(x+h)-f(x)}{h}}{ h} \\ =\frac{f(x+2h)-f(x+h)-f(x+h)+f(x)}{h^2}= \\ \frac{f(x+2h)-2f(x+h)+f(x)}{h^2}=g_1(x) \\ \Delta ^3f (x)=\frac{g_1(x+h)-g_1(x)}{h}= \\ \frac{\frac{f([x+h]+2h)-2f([x+h]+h)+f(x+h)}{h^2}-\frac{f(x+2h)-2f(x+h)+f(x)}{h^2}}{h} \\ = \frac{f(x+3h)-2 f(x+2h)+f(x+h)-f(x+2h)+2f(x+h)-f(x) }{h^3} \\ =\frac{f(x+3h)-3f(x+2h)+3f(x+h)-f(x)}{h^3} =g_2(x) \\ \]

\[\Delta ^n f(x)= \frac{1}{h^n} \sum_{k=0}^n \left(\begin{matrix}n \\ k\end{matrix}\right) (-1)^{n+1} f(x+kh)\]

Answer 3

no it is a little wrong

Answer 4

It is? I think it looks right, this is a completely different approach than what I did for this problem so I dunno. I like this though, it's why I asked, I like seeing other things.

Answer 5

well it works for g2 but g1

Answer 6

the signs are just off

Answer 7

\[\Delta ^n f(x)=\frac{1}{h^n} \sum_{k=0}^{n} \left(\begin{matrix}n \\ k\end{matrix}\right) (-1)^n f(x+[n-k]h)\]
I think that fixes it

Answer 8

But I don't know if that ugly thing set to f(x) would be pretty to look at

Answer 9

Yeah I'm still sorta trying to see if there's some simpler way to derive this equation cause it's sorta hard for me to get the details correct on it like the sign and all that. I think I see how you're 'counting down' in order to get the signs right cause the leading f(x+nh) will always be positive

Answer 10

yep

Answer 11

and those pretty pascal triangle numbers

Answer 12

Ok yeah yeah this makes sense now, perfectly, I see it. :D

So somehow this is true heh... xD
\[ f(x)=\frac{1}{h^n} \sum_{k=0}^{n} \left(\begin{matrix}n \\ k\end{matrix}\right) (-1)^k f(x+[n-k]h)\]

Answer 13

somewhere it is true? it is not true for all x and f right?

Answer 14

I guess I mean, this is just a very gross functional equation, it's not an actual f(x).

\[ f(x)=\frac{1}{h^n} \sum_{k=0}^{n} \left(\begin{matrix}n \\ k\end{matrix}\right) (-1)^k f(x+[n-k]h)\]

Also it seems like we can rewrite it (although not sure if this does anything),

\[ f(x)=\frac{(-1)^n f(x)}{h^n}+\frac{1}{h^n} \sum_{k=0}^{n-1} \left(\begin{matrix}n \\ k\end{matrix}\right) (-1)^k f(x+[n-k]h)\]


\[ \left( 1 - \frac{1}{(-h)^n} \right) f(x) = \frac{1}{h^n} \sum_{k=0}^{n-1} \left(\begin{matrix}n \\ k\end{matrix}\right) (-1)^k f(x+[n-k]h)\]

Answer 15

lol f(x)=0 is a solution

Answer 16

Haha actually it isn't! Specifically for n>1 in \(\Delta^n f(x) =f(x)\) cause \(\Delta f(x) \ne f(x)\) is part of the question :P

Answer 17

I think I'm confused

Answer 18

Possibly, I am not psychic so I can't be sure. You seem to be doing things that make sense so far though!

Answer 19

well I think I'm confused about your condition
what is n and k

Answer 20

I mean I know you want n<k

Answer 21

we want to solve
\[\Delta ^kf(x)=f(x) \text{ where } n<k \text{ and } \Delta ^n f(x) \neq f(x)\]

Answer 22

so in the one I have k=1
but you said n>1...

Answer 23

Ahhh ok so for example

\[\Delta^3 f(x) = f(x)\] while also
\[\Delta^1 f(x) \ne f(x)\]\[\Delta^2 f(x) \ne f(x)\]

Answer 24

ok no proceeding ones can equal ok
I understand now
sorry I'm slow

Answer 25

Maybe I typed it up wrong or confusing my bad!

Answer 26

Slight alteration:
\[ f(x)=\frac{1}{h^n} \sum_{k=0}^{n} \left(\begin{matrix}n \\ k\end{matrix}\right) (-1)^k f(x+[n-k]h)\]
just flopped the n-k to the -1 cause the binomial thing is symmetric
\[ f(x)=\frac{1}{h^n} \sum_{k=0}^{n} \left(\begin{matrix}n \\ k\end{matrix}\right) (-1)^{n-k} f(x+kh)\]

I was thinking about maybe adding this to itself forwards and backwards 'gauss style' but I don't think that will really do anything for us here if that makes sense.

Answer 27

More prettying up, but not really progress in any way, sorry I'm kinda struggling to make this work
\[ f(x)=\frac{1}{(-h)^n} \sum_{k=0}^{n} \left(\begin{matrix}n \\ k\end{matrix}\right) (-1)^{k} f(x+kh)\]

Answer 28

I haven't verified it...
but I'm going to test to see if \[f(x)=(h+1)^\frac{x}{h} \\ \]

Answer 29

:DDD

Answer 30

like I think for this one
\[f(x) \neq \Delta f(x) \text{ but } f(x) = \Delta ^2f(x)\]

Answer 31

\[f(x)=(-h+1)^\frac{x}{h}\] also works for k=2

Answer 32

\[f(x)=c^x \\ h^n c^x=\sum_{k=0}^n \left(\begin{matrix}n \\ k\end{matrix}\right)(-1)^{n-k} c^{x+kh} \]
I wonder if we can play with this...
\[h^n= \sum_{k=0}^n \left(\begin{matrix}n \\ k\end{matrix}\right) (-1)^{n-k}c^{kh} \\ \text{ \let } c^h=m \\ h^n=\sum_{k=0} ^n \left(\begin{matrix}n \\ k\end{matrix}\right)(-1)^{n-k} m^k \\ \]
solve this equation for m
then c

Answer 33

that one thing worked awesomely for the 2nd thingy because it turned out to be a square equal a square (you know for my previous solutions if that makes sense)

Answer 34

\[h^n=(-1+m)^n\]

Answer 35

Do these functions \(g_0, g_1,\ldots, g_{n-1}\) also form some kind of a cyclic group under the operation composition ?

Answer 36

\[h=-1+m \\ h+1=m \\ h+1=c^h\]
oh that ends up being the same thing I just got...

Answer 37

Ahhh I think that's a good observation, yes I think so.

Answer 38

Maybe I should give a hint, \(\Delta\) is a linear operator and I used this fact in finding my solutions.

Answer 39

I am not even sure if my solution is most general, so maybe I should share it and see if we can expand on it with your solution ideas?

Answer 40

I'm not sure I want to see it yet but you can post it if @ganeshie8 wants to see it.

Answer 41

I've just started... still searching for pen and paper :)

Answer 42

so far my most general solution I think is
\[f(x)=c_1 \cdot (h+1)^\frac{x}{h}+c_2 (-h+1)^\frac{x}{h}\]

is this half of yours at least @empty ?

Answer 43

It looks a little different but might be the same, I'm not sure I just got back from the kitchen grabbing some tea.

Answer 44

Yeah, that question you asked earlier is exactly what I have for that case :)

Answer 45

I have to check back tomorrow on this question
I only know how to find solutions in the form c^x

Answer 46

goodnight you guys

Answer 47

Yeah same, that's all I could find too.

Answer 48

Well, I found them in a slightly different way but yeah, ultimately I don't know if there are other solutions out there of different forms.

Answer 49

I suppose I'll go ahead and type up my way to the solution.

Answer 50

I am trying something like this

Since \(\Delta \) is linear, we have
\(\Delta^n f(x)h^n = \Delta^{n-1}f(x+h) - \Delta^{n-1}f(x)\) and @myininaya 's earlier binomial sum follows trivially

Answer 51

\[h\Delta f(x) = f(x+h) - f(x) \implies f(x+h) = (1+h\Delta ) f(x) \]

If we define another operator \(E \) for shifting as \(Ef(x) = f(x+h)\), it follows from above :
\[E = 1+h\Delta\]

Answer 52

same as
\[\Delta = \dfrac{E-1}{h}\]

Answer 53

\[\Delta^n f(x) = \left(\dfrac{E-1}{h}\right)^nf(x)\]

Answer 54

Interesting, I just saw something similar used just yesterday for the first time for motivating the derivation of the generating function for Bernoulli numbers.

Answer 55

I am just playing with these difference operator... i have no clues yet how to find some solutions ...

Answer 56

Yeah, I think I only ever play. I posted my solution (possibly incomplete) here if anyone's curious or wants to avoid looking just to have fun: http://mathb.in/50160

Answer 57

\[f(x) = \sum_{k=0}^{n-1} c_k (he^{i 2 \pi k/n}+1)^{x/h}\]

For first term,\(\Delta t_1 = t_1 \), so the first term doesn't change over the \(n\) iterations

For second term, \(\Delta^2 t_2 = t_2 \), so the second term keeps toggling between \(t_2\) and \(\Delta t_2\)

\(\ldots \)

Since the complex \(n\)th roots of unity form a cyclic group of order \(n\), each term settles back to the starting expression after \(n\) iterations!

Truely awesome !!

Answer 58

Fun! I just wish there was some way to know if this is truly ALL of the solutions or what? I think the major insight for me was thinking like this:

\[\Delta^2 f= \Delta( \Delta f) = \Delta ( af)= a (\Delta f) = a (af) = a^2 f\]

So basically turning \(\Delta ^n f = a^n f\) allowed me to turn composing the operator into simply taking the root of a constant. :P

Answer 59

I see... feels like there must exist many other solutions..

Answer 60

Yeah I agree hmm. I am all outta ideas at the moment.