Notation involving recursive function

Question

Can someone explain to me what this notation means?

I think that for any value of $n$ that is equal or below 3 I just return $n.$ But the second line has me confused.

Answer 1

As you said, for $n = 1$ you have $K_1=1$. Similarly, $K_2=2$ and $K_3=3$.

Than little number is called a subscript and is often used to designate the $n-th$ item in a sequence. The other equation tells you how to continue the sequence. Let's practice two more:

$$ K_4 = K_3 + 2K_2 + 3K_1 = 3+2\cdot 2 + 3\cdot 1 = 10 \\ K_5 = K_4 + 2K_3 + 3K_2 = 10 +2\cdot 3 + 3\cdot 2 = 24 \\ $$ By the way, for large values of $n$, $K_n$ is about $0.29 \cdot (2.3744)^n$.

Answer 2

It's a sequence defined by recursion, i.e. a sequence that calls itself in its definition.

Here the sequence is $K_n =K(N)\colon\Bbb N \to \Bbb N$; while $n\leq 3$ it just return $n$ itself as you stated: $$K_0=0 \quad K_1=1 \quad K_2 = 2 \quad K_3 = 3$$ For $n=4$, for example: $$K_n = K_1 + 2\,K_2 + 3\,K_3 = 6,$$ or, for $n=5$, $$K_5 = K_2 + 2\,K_3 + 3\,K_4 = 2 + 2\cdot 3 + 3\cdot 6 = 24.$$

Answer 3

The explanations of the notation above are OK, but the meaning of the process represented by $K_n=n, n<4 \ and \ K_n=K_{n-1}+2K_{n-2}+3K_{n-3}, n>3$

is quite interesting: $K_n$ is a weighted moment of the three previous values, giving the largest weight (3) to the oldest one and the smallest weight (1) to the newest one. It can be written in a compacted form as:

$K_n=n$ for $n<4$

and

$K_{n} = \sum_{i=1}^{3} i K_{n-i}$ for $n>3$

The plot of $K_n$ vs $n$ in log scale is linear for $n>3$, so it is an exponential (10 base) function of $n$.

In fact, it is approximated by

$K(n)=10^{a+bn}$, with $a=-0.4151404$ and $b=0.3537851$.

as shown in the figure below (in red the approximation)

K(n) vs n (log plot) real and approximated curve

To obtain the exact closed-form of the recurrence is quite hard work, but feasible. For this reason, sometimes an approximation helps in avoiding costly iterative calculations for large $n$ values.