| I don't think you're thinking about these concepts in a useful way. Yes, factorials can be defined through recursion. But so can multiplication of non-negative integers: def mult(a, b):
if a == 0 or b == 0: return 0
if a == 1: return b
return mult(a-1, b) + b
>>> mult(5, 9)
45
Furthermore, factorials can alternatively be defined through the Gamma function, which supports more than just the integers and isn't defined recursively. https://en.wikipedia.org/wiki/Gamma_function .> the simplest (AFAIK) recurrence relationship ...that can be produced. The positive integers is even easier. For n >= 0: F(0) = 0
F(n) = 1 + F(n-1)
> What's very interesting about the Fibonnaci SequenceAnother interesting thing about the Fibonnaci Sequence is that it has a closed-form solution, given in your OEIS link as: F(n) = ((1+sqrt(5))^n - (1-sqrt(5))^n)/(2^n*sqrt(5))
or see https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_e... .It is also non-polynomial. In the limit, it approaches a simple exponential. Nor is it bounded by a polynomial, meaning that if you pick any positive integer p and any constant C, and define g(n) = C n^p then for a large enough n you will find that |g(n)| < |F(n)| . Furthermore, A000435 , with its n^n - like form, grow even faster than exponential. It's similar to factorial growth. > as a fellow Mathematician I am not a mathematician. Neither are you. > s to figure out when/where/why the number table / difference table / triangle / fan -- fails -- between the simplest of all recurrence relationship formula, the Fibonnaci sequence -- and this one Consider f(n) = f(n-1) + 1 where f(0) = 0. This is the sequence 0, 1, 2, 3, .... This addition of 1 can be seen trivially in the difference table. Consider f(n) = f(n-1) + f(n-1) with f(1) = 1. This is the sequence 1, 2, 4, 8, 16, 32, or 2^n, which is an exponential function. Consider the Fibonacci function f(n) = f(n-1) + f(n-2) with f(1) = f(2) = 1. This uses an addition of the two previous numbers. It approaches an exponential function as n gets larger. Consider f(n) = n * f(n-1) with f(1) = 1 This is the factorial. It grows faster than the exponential function. Because the last one uses a multiplication instead of addition, a difference table (which is based on subtraction) won't show the pattern. The inverse of multiplication is division, so use a division table. > deeply recursive algorithms These are not deeply recursive. For an example of those, see the Ackermann function. https://en.wikipedia.org/wiki/Ackermann_function , which is not primitive recursive like functions we've discussed so far. |
Well -- that looks like the problem then!
And the solution -- use a division table -- as you said.
Point is, is that the method shown in the Mathologer video -- does in fact work for every integer sequence defined by polynomials, including some of those that are non-polynomial and involve recursion -- as long as that recursion involves only addition and not multiplication...
In other words, sequence algorithms which are recursive and involve multiplication -- fail.
But then the next question must be -- is there a generalized algorithm for the construction of Mathologer's tables, which creates a subtraction table on the one hand and a divison table on the other?
Which points to the following problem/question:
Given an arbitrary integer sequence -- how can we know that the algorithm that generates it -- uses recursion and multiplication? (without knowing anything else about it -- other than the given sequence of numbers?)
?
>"I don't think you're thinking about these concepts in a useful way."
Define "useful". <g> :-)