I have the following recursive definition for the construction of EVEN Numbers-
[RULE 1]: 2 is an EVEN number.
[RULE 2]: If x is an EVEN number and y is an EVEN number, then x+y is also an EVEN number.
In how many ways can the number 14 be derived using the above definition? For example, one way to derive 14 is
2 is in EVEN,
2+2 = 4 is in EVEN,
4 + 4 = 8 is in EVEN,
8 + 4 = 12 is in EVEN
and finally 12 + 2 = 14 is in EVEN.
I tried by trial-and-error and I could get a answer (9 ways) for this problem but
(1) I am not sure if my answer is correct
(2) I failed to find a general pattern i.e given a EVEN number n, does there exist a function f(n) which will give me the number of ways to derive n?
$f(n)$: Number of ways the integer $n$ can be derived from the above definition.
For every even number $n$ we must consider the following partitions recursively:
$$ n = (n-2) + 2\\ n = (n-4) + 4\\ n = (n-6) + 6\\ \cdots\\ n = s + t $$
where $s$ and $t$ are defined as follows:
$$ (s, t) = \left\{ \begin{array}{ll} (\frac{n}{2}, \frac{n}{2}) & \mbox{if } \frac{n}{2}~is~even \\ (ceil(\frac{n}{2}), floor(\frac{n}{2})) & otherwise \end{array} \right. $$
They are defined in this way because I presume that the order of the numbers in the each partition doesn't matter. If the order is important to you, continue partitions to $n = 2 + (n-2)$ instead.
But this is the top level of our recursion. After using each partition we must continue partitioning the parts in the same way. So we can define the $f(n)$:
$$ f(n) =\Sigma_{i=1}^{t/2}f(n-2i) + f(2i)\\ f(2) = 1 $$