Print this problem set out (there are 7 problems!) and answer the
problems on the given sheet.
-
Compute the first 8 terms (index 0 through 7) of:
$$
\begin{array}{rcl}
a(n) & = & 2\cdot a(n-1) + \lfloor n/2 \rfloor\\
a(0) & = & 1
\end{array}
$$
-
Compute the first 8 terms (index 0 through 7) of:
$$
\begin{array}{rcl}
a(n) & = & 2\cdot a(n-2) + n\\
a(0) & = & 0\\
a(1) & = & 1\\
\end{array}
$$
-
Given the recurrence relation for $c(\cdot)$ below, and the
hypothesis for its closed form,
give an inductive proof that the hypothesis is correct.
$$
\text{recurrence relation: }
c(n) = c(n-1) + (-1)^n,\ \ c(0) = 1
\ \ \ \text{ hypothesis: } c(n) = (1 + (-1)^n)/2
$$
-
Given the recurrence relation for $f(\cdot)$ below, expand and
guess a closed form.
(You do not have to prove it is correct, though don't you want
to?)
$$
f(n) = n\cdot f(n-1),\ \ f(0) = 1
$$
-
Write the explicit sum and the actual value of
$\Sigma_{i=2}^5 i^2$.
-
Write the explicit sum and the actual value of
$\Sigma_{i=2}^5 i^2$.
-
"$\Sigma$" has some really nice properties. Here are two (I
was *this* close to asking you to prove them!):
-
$\Sigma_{i=a}^b \left(a\cdot f(i)\right)
= a \cdot \Sigma_{i=a}^b f(i)
$
-
$\Sigma_{i=a}^b \left(f(i) + g(i)\right)
= \Sigma_{i=a}^b f(i) + \Sigma_{i=a}^b g(i)
$
Use these facts (and the close form solutions for $S(n)$ and
$P(n)$ from the lecture notes) to give a nice closed form
solution to
$$
\Sigma_{i=1}^n \left(
2\cdot 5^i - 5i
\right)
$$