How many ways to reach an integer by addition and multiplication Inspired by the title of a recent question, which turned out to be about something else.
Start with any number.  Then repeatedly add any positive integer or multiply by any integer greater than $1$.
Let $f(n)$ be the number of ways to reach $n$.
For example, $f(3)=6$ because $$3=2+1=1+2=(1+1)+1=(1×2)+1=1×3$$
The first few values are https://oeis.org/A348378
$$1,3,6,15,27,63,117,...$$
On one hand, it always seems to be a multiple of $3$.  On the other, the first twenty terms are close to $0.988×2^n$ with an oscillation of size around $1.4^n$.
How would one prove either of those things?
 A: An integer $n \ge 1$ can be reached from $j < n$ by adding a positive integer, and also by multiplying $j$ with a positive factor if $j$ is a divisor of $n$.
Therefore the function can be recursively defined as $f(0) = 1$ and
$$
 f(n) = \sum_{0 \le j < n} f(j) + \sum_{\substack{1 \le j < n\\ j \mid n}} f(j)
$$
for $n \ge 1$.
If $n \ge 2$ then $f(0) = 1$ occurs in the first sum, and $f(1)=1$ occurs in both sums, so that
$$ \tag{$*$}
 f(n) = 3 + \sum_{2 \le j < n} f(j) + \sum_{\substack{2 \le j < n\\ j \mid n}} f(j)
$$
for $n \ge 2$.
With respect to the first question:
It follows from $(*)$ and induction that $f(n)$ is a multiple of three for all $n \ge 2$:

*

*$f(2) = 3$ since the two sums on the right are empty.

*For $n \ge 3$ is $f(n)$ equal to $3$ plus a sum of terms $f(j)$ with $2 \le j < n$.

With respect to the second question I have only a very rough estimate so far:
$$
\sum_{j=0}^{n-1} f(j) \le f(n) \le 2 \sum_{j=0}^{n-1} f(j)
$$
implies that
$$
 2^{n-1} \le f(n) \le 2 \cdot 3^{n-1}
$$
for $n \ge 1$.
