Add Me!Close Menu Navigation

More Sequences

Find a closed form formula for the recurrence relation

     \begin{align*} x_1 &= 1 \\ x_n &= \begin{cases} x_{n-1} + n &\mbox{if $n$ odd} \\  x_{n-1} + n - 1 & \mbox{if $n$ even} \end{cases}  \end{align*}

1. Let’s guess at an answer

Let’s look at the expansion of the recurrence

    \begin{align*} x_1 &= 1\\ x_2 &= x_1 + 1 \\ x_3 &= x_2 + 3 \\ x_4 &= x_3 + 3 \\ x_5 &= x_4 + 5 \\ x_6 &= x_5 + 5 \\ & \vdots \end{align*}

the following table will give the values of x_n

    \[\begin{tabular}{c|c|c|c|c|c|c|c|c} n & 1 & \boxed 2 & 3 & \boxed 4 & 5 & \boxed 6 & 7 & \boxed 8 \\ \hline x_n&1&2&5&8&13&18&25&32 \end{tabular}\]

Once again, we see that the boxed indexes \hat n display the property that x_{\hat n} = \frac{\hat n^2}{2}. Hence, for even values of n, the equation x_n = \frac{n^2}{2} holds. We now use this to guess that in general

    \begin{align*} x_n &= \begin{cases} \frac{n^2}{2} & \mbox{$n$ even}\\ \frac{n^2 + 1}{2} & \mbox{$n$ odd} \end{cases} \\ &= \left\lceil \frac{n^2}{2} \right\rceil \end{align*}

2. Show that x_n = \left\lceil \frac{n^2}{2} \right\rceil

We can prove this inductively on values of even n. Informally, we will use x_n = x_{n-1} + n - 1 = x_{n-2} + 2(n-1) for n even to show that our proposition holds for even values of n, and then use those even values to confirm that the proposition holds for odd n as well.

Show that x_n = \left\lceil \frac{n^2}{2} \right\rceil for even values of n

We need to prove the proposition P_n \equiv x_n = \left\lceil \frac{n^2}{2} \right\rceil is true for even values of n.

As our starting point, it is obvious that P_2 \equiv x_2 = \left\lceil \frac{4}{2} \right\rceil = 1 + 1 holds. We now outline the induction steps.

Show that P_{n-2} \implies P_n

    \begin{align*} x_n &= x_{n-2} + 2(n-1) & \mbox{\tiny{substitute $x_{n-2}$ via the induction hypothesis}}\\ &= \left\lceil \frac{(n-2)^2}{2} \right\rceil + 2(n-1) &\mbox{$n-2$ even}\\ &= \frac{(n-2)^2}{2} + 2(n-1) \\ &= \frac{n^2-4n + 4}{2} + \frac{4(n-1)}{2} \\ &= \frac{n^2}{2} \\ &\implies P_n \end{align*}

This concludes our proof that x_n = \left\lceil \frac{n^2}{2} \right\rceil for even values of n \blacksquare

Show that x_n = \left\lceil \frac{n^2}{2} \right\rceil for odd values of n

Because n odd, this becomes equivalent to showing x_n = \frac{n^2+1}{2}. For odd values of n, we’ve already shown P_{n-1}, hence we only need to show P_{n-1} \implies P_n

    \begin{align*} x_n &= x_{n-1} + n &\mbox{\tiny{Discharge $P_{n-1}$ here}}\\ &= \frac{(n-1)^2}{2} + n \\ &= \frac{n^2 - 2n + 1}{2} + \frac{2n}{2} \\ &= \frac{n^2 + 1}{2} \\ &\implies P_n \end{align*}

This concludes our proof that x_n = \left\lceil \frac{n^2}{2} \right\rceil for odd values of n \blacksquare

Because x_n = \left\lceil \frac{n^2}{2} \right\rceil for both even and odd values of n, then naturally, x_n = \left\lceil \frac{n^2}{2} \right\rceil for all natural values of n. \blacksquare

Posted By Lee

Woosh