# Finding the exact symbolic formula for a function defined recursively

Let me introduce the problem.

I have the following functions;

The first one is defined recursively

$$h(i,j):=\frac{i-1}{j+1}h(i+2,j-2)$$ and $$h(i,0)=1$$ where $$i$$ and $$j$$ are even integers, greater than $$0$$.

The second one is a sum

$$f(n)=\sum_{k=0}^n {n\choose k}\ h(2k,2n-2k)$$ where $$n$$ is a positive integer.

My goal is to find a closed form expression for the function $$f(n)$$. To implement these functions I have written the following code:

h[i_, 0] := 1
h[i_, j_] := ((j - 1)/(i + 1))*h[i + 2, j - 2]
Sum[Binomial[n, k]*h[2 k, 2 n - 2 k], {k, 0, n}]


But after running this code I am greeted with the following lovely message

$RecursionLimit::reclim2: Recursion depth of 1024 exceeded during evaluation of -2040-2 k+2 n.  I believe there must be an exact formula for the function, based on the physical problem that these functions emerge from. I am hoping that the function $$f(n)$$ can be written as fraction of polynomials in $$n$$. So where is the problem? Is it with my implementation or the functions defined above are hopeless, in the sense that there is no closed form, mathematically? • Version 12.1 I can not reproduce your problem. Try with a new kernel. Mar 12, 2021 at 14:54 • @DanielHuber Do you mean you have found a closed form expression for$f(n)\$? Mar 12, 2021 at 14:57
• @DanielHuber Would you mind trying again? I have made edited my code. Mar 12, 2021 at 14:58
• @MariuszIwaniuk Why do I need 2 conditions? Mar 12, 2021 at 15:09

Clear["Global*"]

h[i_, 0] := 1
h[i_, j_] := ((j - 1)/(i + 1))*h[i + 2, j - 2]


Use the recursion to generate a sequence for even values of j

seq = {#, h[i, #]} & /@ Range[0, 10, 2]

(* {{0, 1}, {2, 1/(1 + i)}, {4, 3/((1 + i) (3 + i))}, {6,
15/((1 + i) (3 + i) (5 + i))}, {8,
105/((1 + i) (3 + i) (5 + i) (7 + i))}, {10,
945/((1 + i) (3 + i) (5 + i) (7 + i) (9 + i))}} *)


Use FindSequenceFunction to generalize from the sequence

h2[i_, j_] = FindSequenceFunction[seq][j] //
Simplify

(* Pochhammer[1/2, j/2]/Pochhammer[(1 + i)/2, j/2] *)


Verifying the equivalence

And @@ (h[i, #] == h2[i, #] & /@ Range[0, 100, 2] // Simplify)

(* True *)

f[n_] = Sum[Binomial[n, k]*h2[2 k, 2 n - 2 k], {k, 0, n}]

(* (Sqrt[π] n!)/(1/2 (-1 + 2 n))! *)


EDIT: For a slightly simpler form

f[n_] = f[n] // Simplify

(* (Sqrt[π] n!)/(-(1/2) + n)! *)


Plotting f

Plot[f[n], {n, -1/2, 20}]
`