# Thread: Solve the recurrence relation

1. ## Solve the recurrence relation

Solve the recurrence relation

$\displaystyle \sum_{k=1}^n \binom{n}{k} a(k) = \frac{n}{n+1}$

I have two methods, one is general , by looking at first few terms and prove my deduction by induction .

I want to discuss the second one , I construct

$\displaystyle a(k) = c \int_0^1 [f(t)]^k~dt$ so we have

$\displaystyle c \int_0^1 \sum_{k=1}^n \binom{n}{k} [f(t)]^k~dt = \frac{n}{n+1}$

$\displaystyle c \int_0^1 ( [ 1 + f(t)]^n - 1) ~dt = \frac{n}{n+1}$

Let $\displaystyle c=-1$ , then we obtain

$\displaystyle \int_0^1 [ 1 + f(t)]^n ~dt = \frac{1}{n+1}$

I know that $\displaystyle \int_0^1 t^n ~dt = \frac{1}{n+1}$

so i let $\displaystyle 1 + f(t) = t$ and i find that

$\displaystyle a(k) = -\int_0^1 (t-1)^k~dt = \frac{(-1)^{k+1}}{k+1}$

My problem is since $\displaystyle \int_0^1 [g(t)]^n~dt = \frac{1}{n+1}$ has many solutions , if we choose other solution , will we arrive at the same destination ?

2. Originally Posted by simplependulum
My problem is since $\displaystyle \int_0^1 [g(t)]^n~dt = \frac{1}{n+1}$ has many solutions , if we choose other solution , will we arrive at the same destination ?
Yes, for a fixed $\displaystyle n$. But how many satisfy that for all $\displaystyle n\in \mathbb{N} ?$

It's true that if you have one such function then it generates a solution. -and well, in this case you can check that each $\displaystyle a(k)$ is unique, once you you have found a function like that, you are done. But on a different problem -another recurrence- there might not be a function satisfying $\displaystyle a(k)=c\cdot \int_0^1\{f(t)\}^kdt$.

About the original equation, if you have 2 e.g.f s (exponential generating functions) $\displaystyle A(x)$ and $\displaystyle B(x)$ -generated by $\displaystyle a_k$ and $\displaystyle b_k$ respectively-, then $\displaystyle A(x)\cdot B( x) = \sum_{n=0}^{\infty}\left(\sum_{k=0}^n\binom{n}{k}\ cdot a_k \cdot b_{n-k}\right)\cdot \tfrac{x^n}{n!}$. In your case pick $\displaystyle B(x)=e^x$ - note that $\displaystyle a(0)=0$ ...-

3. Other solution

iff you have something like

$\displaystyle \sum^n_{k=0} {n \choose k}a(k) =f(n)$

then

$\displaystyle a(k)=\Delta^k f(0)$
where $\displaystyle \Delta^k f(0)$ is the difference operator

$\displaystyle \Delta^0 f(x) =f(x)$
$\displaystyle \Delta^{n+1} f(x)= \Delta^n f(x+1)-\Delta^n f(x)$
for all n in N.

It's Newton interpolation formula