Ackerman function 2

Algebra Level 4

Let's reiterate about Ackerman function \(\mathcal{A}\).

\(\mathcal{A}(m,n) = \begin{cases} n+1 & \text{if } m = 0 \\ \mathcal{A}(m-1, 1) & \text{if } m > 0, n = 0 \\ \mathcal{A}(m-1, \mathcal{A}(m-1, n-1)) & \text{if } m > 0, n > 0 \end{cases}\)

Unlike what's suspected, this function actually doesn't grow as quickly as Ackermann function!

Let \(\displaystyle S(n) = \sum_{i=0}^n \sum_{j=0}^n \mathcal{A}(i,j)\). It turns out that \(S(n)\) is a polynomial for all sufficiently large \(n\); that is, there exists some integer \(N\) and a polynomial \(P\) such that for all integer \(n > N\), \(S(n) = P(n)\). The sum of the coefficients of \(P(n)\) can be expressed as \(\frac{a}{b}\) for some positive integers \(a,b\) that are relatively prime. Compute \(a+b\).


Problem Loading...

Note Loading...

Set Loading...