# Math Help - Solve the recurrence relation

1. ## Solve the recurrence relation

Solve the recurrence relation

$\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

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

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

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

Let $c=-1$ , then we obtain

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

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

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

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

My problem is since $\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 $\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 $n$. But how many satisfy that for all $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 $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 $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) $A(x)$ and $B(x)$ -generated by $a_k$ and $b_k$ respectively-, then $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 $B(x)=e^x$ - note that $a(0)=0$ ...-

3. Other solution

iff you have something like

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

then

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

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

It's Newton interpolation formula