Finding the exact symbolic formula for a function defined recursively

Question

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?

Answer 1

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}]