Let $S_n:=X_1+\dots+X_n$ (with $S_0:=0$), where $X_1,X_2,\dots$ are iid Bernoulli random variables with parameter $1/2$. Let then
\begin{equation*}
T:=\inf\{n\ge0\colon S_n>f(n)\}.
\end{equation*}
You are interested in $P(T=n)$.
We have
\begin{align*}
P(T=n)&=P(S_0\le f(0),\dots,S_{n-1}\le f(n-1),S_n>f(n)) \\
&=\frac1{2^n}\,\sum_{x_1=0}^1\dots\sum_{x_n=0}^1 I_n(x_1,\dots,x_n), \tag{$*$}
\end{align*}
where
\begin{equation*}
I_n(x_1,\dots,x_n):=
1(s_0\le f(0),\dots,s_{n-1}\le f(n-1),s_n>f(n))
\end{equation*}
and $s_k:=x_1+\dots+x_k$ (with $s_0:=0$).
The $n$-fold sum in ($*$) provides an analytic expression for $P(T=n)$. However, this expression is rather complicated, and the calculation based on ($*$) requires an exponential in $n$ number of arithmetic operations.
It is much more effective to compute $P(T=n)$ recursively. First here, note that for natural $n$
\begin{equation*}
P(T=n)=P_{n-1}-P_n,\tag{0}
\end{equation*}
where
\begin{equation*}
P_n:=P(T>n)=P(T\ge n+1).
\end{equation*}
In turn,
\begin{equation*}
P_n=\sum_{x=0}^{g(n)}p_{n,x},\tag{1}
\end{equation*}
where
\begin{equation*}
g(n):=\min(n,f(n))
\end{equation*}
and
\begin{equation*}
p_{n,x}:=P(T>n,S_n=x).
\end{equation*}
For $n=1,2,\dots$
\begin{align*}
p_{n,x}&=\sum_{y=0}^\infty P(T>n-1,S_{n-1}=y,S_n=x)1(x\le f(n)) \\
&=P(T>n-1,S_{n-1}=x,S_n=x)1(x\le f(n)) \\
&+P(T>n-1,S_{n-1}=x-1,S_n=x)1(x\le f(n)) \\
&=P(T>n-1,S_{n-1}=x,X_n=0)1(x\le f(n)) \\
&+P(T>n-1,S_{n-1}=x-1,X_n=1)1(x\le f(n)) \\
&=P(T>n-1,S_{n-1}=x)P(X_n=0)1(x\le f(n)) \\
&+P(T>n-1,S_{n-1}=x-1)P(X_n=1)1(x\le f(n)) \\
&=\frac{p_{n-1,x}+p_{n-1,x-1}}2\,1(x\le f(n)).
\end{align*}
Thus, we have a recursive difference scheme to determine $p_{n,x}$: for all $x=0,1,\dots$,
\begin{equation*}
p_{0,x}=1(x\le f(0),x=0)
\end{equation*}
and, for all $n=1,2,\dots$,
\begin{align*}
p_{n,x}=\frac{p_{n-1,x}+p_{n-1,x-1}}2\,1(x\le f(n)).
\end{align*}
So, to compute all nonzero values of $p_{n,x}$ for all $x=0,1,\dots$ by this scheme, we only need $O(\sum_{k=0}^n g(n))=O(n^2)$ arithmetic operations. Having computed the values of $p_{n,x}$, we use (0) and (1) to quickly finish the calculation of the probability of interest, $P_T(n):=P(T=n)$.
This way, Mathematica computes $P_T(1),\dots,P_T(100)$ (for $f(n)\equiv n/2+\sqrt n$) in about 0.11 sec, and then $P_T(1),\dots,P_T(200)$ in about 0.37 sec:
In contrast, using formula ($*$), Mathematica takes about 0.56 sec to compute just $P_T(1),\dots,P_T(10)$ (for the same $f$) and about 3.2 sec to compute $P_T(1),\dots,P_T(12)$.
