Which of the following recurrence relations is linear?
an=an−12+1a_n = a_{n-1}^2 + 1an=an−12+1
an=2an−1+an−2+na_n = 2a_{n-1} + a_{n-2} + nan=2an−1+an−2+n
an=an−1a_n = \sqrt{a_{n-1}}an=an−1
an=an−1⋅an−2a_n = a_{n-1} \cdot a_{n-2}an=an−1⋅an−2