Fibonacci Numbers Induction?

Question

Show that $a_n=n^2+n+1$ satisfies \begin{cases} a_0=1\\ a_k=a_{k-1}+2k & \text{for $k>0$} \end{cases}

I want to use induction to solve this problem. but I don't know what my base will be since $k$ has to be greater than $1$. Should my base case be when $k=1$ (assuming this question uses integers).

Please give me a hint on how to solve this.

Answer 1

Base cases

k=0

$a_0 = 0 + 0 + 1 = 1$. Check.

k=1

$a_1 = 1 + 1 + 1 = 1 + 2 = a_0 + 2k$. Check.

Induction step:

Assume this holds for all $n \le k$ for some k. Then

$a_{k+1} = (k+1)^2 + (k+1) + 1 = ....$....

Answer 2

The second formula can be written, equivalently, $$ a_k-a_{k-1}=2k \qquad \text{for $k>0$} $$ Now just plug in the definition: \begin{align} a_{k}-a_{k-1} &=(k^2+k+1)-((k-1)^2+(k-1)+1)\\ &=k^2+k+1-k^2+2k-1-k+1-1\\ &=2k \end{align}

Answer 3

You didn't read carefully.

$a_k$ is defined in terms of $a_{k-1}$ when $k>1$, but $a_k$ is directly defined when $k=0$. So a base case with $k=0$ is perfectly possible.

Indeed,

$$a_0=1=0^2+0+1$$ is true.

---

If you insist on starting from $k=1$, then you need to compute $a_1$, obtained by

$$a_1=a_0+2\cdot1=3.$$ Then

$$a_1=3=1^2+1+1$$ is true.

But you still need to show that the property holds for $a_0$, as this is not covered by the base case nor by the induction !

Answer 4

$a_0 = 0^2 + 0 + 1 = 1$

$a_1 = 1^2 + 1 + 1 = 3$

$a_1 = a_0 + 2(k) = 1 + 2(1) = 3$

$a_k = k^2 + k + 1$

$a_{k+1} = (k+1)^2 + (k+1) + 1$

[\begin{array}{lllllllllllllllllll} a_{k+1} & = & (k+1)^2 + (k+1) + 1 \\ & = & k^2 + 3k + 3 \\ & = & k^2 + (k + 2k) + (1+2) \\ & = & (k^2 + k + 1) + (2k + 2) \\ & = & a_k + (2k + 2) \\ & = & a_k + 2(k+1) \\ \end{array}]