Formulating a recursive definition

Question

Let Σ(k) = 1 + 3 + 5 + ... + (2k+1) be the sum of all odd natural numbers from 1 up to and including (2k+1). Formulate a recursive definition for Σ including both the base case Σ(0) = 1 and a (k+1)th case.

Base case: Σ(0) = 1 ⇒ 0 + 1 ⇒ 2(0) + 1
so the base case holds.

How do I formulate a recursive definition for the (k+1)th case?

Answer 1

"How do I formulate a recursive definition for the $(k+1)^\text{th}$ case?"

You do it by writing $f_{k+1}$ in terms of $f_k$:

$$f_k = \sum_{n=0}^{k} 2n+1$$ $$f_{k + 1} = \text{???}$$

Figure out the "???"

$$f_{k+1} = \sum_{n=0}^{k+1} 2n+1$$

$$f_{k+1} = g(f_k) \tag{A}$$

Now you want to figure out $g$, because $g$ is what relates $f_k$ and $f_{k+1}$. So use the known formulas for $f_k$ and $f_{k+1}$ to figure out what $g$ should be. If you need more info here is a hint:

To convert $f_k$ into $f_{k+1}$, you need to add something. So ultimately you need to find $f_{k+1} = f_k + \text{???. }$ Subtract the common terms from each side.

If you really need to see the final answer:

$f_{k+1} = f_k + h(k)$

---

$\sum_{n=0}^{k+1} 2n+1 = \sum_{n=0}^{k} 2n+1 + h(k)$

---

$\left(\sum_{n=0}^{k} 2n+1\right) + 2(k+1)+1= \left(\sum_{n=0}^{k} 2n+1\right) + h(k)$

---

$2(k+1)+1= h(k)$

---

$f_{k+1} = f_k + 2k+3$

Answer 2

Your base case value is somewhat offpoint.

The idea of a recursive function is one that will use previous values to ascertain later ones.

For example,

\begin{align} &\sum(2) = 1+3+5 = 9 = \sum(1) + 2(1)+3\\ &\sum(3)=1+3+5+7=16=\sum(2)+2(2)+3 \end{align} In general, $\sum(k+1)$ will be obtained similarly based on $\sum(k)$, as André explains in the comments. I'll leave it up to you to prove $$\sum(k+1) = \sum(k) + 2k+3$$

Answer 3

Hint: $(k+1)^2-k^2=2k+1$

The recursive definition for $\Sigma(k)$ would be $$ \Sigma(k)=\Sigma(k-1)+2k+1\tag{1} $$ since that is the same as saying $$ \overbrace{1+3+5+\dots+(2k+1)}^{\Sigma(k)}=\overbrace{1+3+5+\dots+(2k-1)}^{\Sigma(k-1)}+(2k+1)\tag{2} $$

Apply the hint to $(1)$ for a closed form for $\Sigma(k)$.

Answer 4

Let $k = 1, 2, 3, \ldots$ be the sequence of natural numbers. We have the recursive formula

\begin{align*} &s(k) = 2k-1,\\ &\Sigma(0) = 0,\\ &\Sigma(k) = \Sigma(k-1) + s(k). \end{align*}

Then, computing $\Sigma(k)$ from $k=1$ to $k=6$, we obtain

$k=1 \quad s(1)=1 \quad \Sigma(1)=1$

$k=2 \quad s(2)=3 \quad \Sigma(2)=1+3=4$

$k=3 \quad s(3)=5 \quad \Sigma(3)=1+3+5=9$

$k=4 \quad s(4)=7 \quad \Sigma(4)=1+3+5+7=16$

$k=5 \quad s(5)=9 \quad \Sigma(5)=1+3+5+7+9=25$

$k=6 \quad s(6)=11 \quad \Sigma(6)=1+3+5+7+9+11=36$

I hope that you find it useful.