Strong Induction proof : $x_k = 1/2(x_{k+1}+x_{k-1})-1$ holds for all integers $k∈Z_{≥0}$

Question

I have just started to learn how to do strong induction. I am struggling to fully understand how to properly do it though. I am trying to work on this exercise where I must prove $x_k = 1/2(x_{k+1}+x_{k-1})-1$ holds for all integers $k∈Z_{≥0}$. The terms are: $0,1,4,9,16...$ The term $x_1 = 1$ was given in the question but all the others were solved for.

I have so far defined a base case of $k=0$ and $k=1$ that holds true. I picked $0$ because it's the minimum value of $k$ and I picked $1$ because I thought I needed too, but I am not sure if it was necessary or why it would be necessary.

I then did the strong induction hypothesis where I state that $P(k)$ is true for all integers such that $0≤k≤n$, where $n∈Z$ such that $n≥1$. I picked $1$ because it's the largest base case value, but I am not sure if it is correct since I am unsure about the base case itself.

After this point, I am not sure how to really apply induction. I tried it many times but my proof doesn't look right.

I really need help on solving this, I am more comfortable with weak induction. I plan to use this solution as a reference for when I solve other problems, so I will be using it as an example to refer back too when I get stuck on tougher problems.

Thank you for any solutions or help provided, I really appreciate it.

Answer 1

Due to the use of $2$ previous index values (i.e., $x_k$ and $x_{k-1}$) in the sequence definition compared to the one with the highest index (i.e., $x_{k+1}$), when using strong induction, you correctly stated that you will need to define $2$ base cases (in general, the number of previous values in the definition determines the minimum number of base cases which are required). As your question statement implied (and ironX's question comment also stated), the hypothesis is that, with

$$x_k = \frac{x_{k+1} + x_{k-1}}{2} - 1 \tag{1}\label{eq1A}$$

and initial values of $x_0 = 0$ and $x_1 = 1$, we then have

$$x_k = k^2 \tag{2}\label{eq2A}$$

for all integers $k \ge 0$.

The $2$ initial, base values of $x_0$ and $x_1$ both satisfy \eqref{eq2A}. Next, the induction hypothesis is to assume \eqref{eq2A} holds for all non-negative integers $k \le n$ for some integer $n \ge 1$, as you already stated in your question text. To use this, first rearrange \eqref{eq1A} as

$$\begin{equation}\begin{aligned} 2x_k & = x_{k+1} + x_{k-1} - 2 \\ x_{k+1} & = 2x_k - x_{k-1} + 2 \end{aligned}\end{equation}\tag{3}\label{eq3A}$$

The induction hypothesis has $x_n = n^2$ and $x_{n-1} = (n-1)^2$, so using this and $k = n$ in \eqref{eq3A} gives

$$\begin{equation}\begin{aligned} x_{n+1} & = 2x_{n} - x_{n-1} + 2 \\ & = 2(n^2) - (n-1)^2 + 2 \\ & = 2n^2 - (n^2 - 2n + 1) + 2 \\ & = 2n^2 - n^2 + 2n - 1 + 2 \\ & = n^2 + 2n + 1 \\ & = (n + 1)^2 \end{aligned}\end{equation}\tag{4}\label{eq4A}$$

This shows \eqref{eq2A} then also holds for $k = n + 1$, completing the induction step. Thus, this proves by strong induction that \eqref{eq2A} is true for all $k \ge 0$.

Answer 2

The problem is to prove that if $x_k=k^2$ and $x_k=\frac{x_{k+1}+x_{k-1}}{2}-1$ then $x_{k+1}=(k+1)^2$, given $x_0=0, x_1=1$

$P(k): x_k=k^2\wedge x_k=\frac{x_{k+1}+x_{k-1}}{2}-1\Rightarrow x_{k+1}=(k+1)^2$

$P(k+1): x_{k+1}=(k+1)^2\wedge x_{k+1}=\frac{x_{k+2}+x_{k}}{2}-1\Rightarrow x_{k+2}=(k+2)^2$

You need to solve for $x_{k+2}$:

$(k+1)^2=\frac{x_{k+2}+k^2}{2}-1\Rightarrow ...x_{k+2}=(k+2)^2$

Therefore, $P(k)\Rightarrow P(k+1)$