Recurrence Relation: Hᵥ = 2ᵛ - Hᵥ₋₁ This problem has been giving me a headache for days. My teacher has taught us the plug-and-chug method of working these problems out and eventually finding a closed form.
However the " - Hᵥ₋₁ " is really throwing me off. My Plug and chug comes out like this:
H₀ = 1 ; H₁ = 2¹ - 1 = 1 ; H₂ = 2² - (2¹ - 1) = 2² - 2¹ + 1 = 3 ; H₃ = 2³ - (2² - 2¹ + 1) = 2³ - 2² + 2¹ - 1 = 5 ......
I've worked out and been staring at this equation for hours: Hᵥ = 2ᵛ - 2^(v-1) + 2^(v-2) - 2^(v-3) + ... + ((-1)^(v-1))2 + (-1)ᵛ
I know the formula that 1 + r + r² + r³ + ... + rᵛ = (r^(v+1) - 1)/(r - 1) and I've tried to manipulate it to fit my problem but I just cannot figure it out. Please someone help. Anything is appreciated.
 A: $H_n+H_{n-1}=2^n$ thus $(-1)^nH_n-(-1)^{n-1}H_{n-1}=(-1)^n2^n$. Suming this gives
$$ \begin{aligned} H_n&=(-1)^n\left(H_0+\sum_{k=1}^n (-2)^k\right) \\&=(-1)^n\left(H_0-1+\frac{(-2)^{n+1}-1}{(-2)-1}\right)\\ &=(-1)^n\left(H_0-1+\frac{1}{3}(1-(-2)^{n+1})\right) \\&=\frac{1}{3}\left(2^{n+1}+(-1)^n\right) \end{aligned}$$
since $H_0=1$
A: I assume that, in addition to knowing the formula:
$$(r-1)(r^v+r^{v-1}+\ldots+r^2+r+1)=r^{v+1}-1$$
you also know a similar formula (easy to derive from the previous by using $-r$ instead of $r$ or by checking directly):
$$(r+1)(r^v-r^{v-1}+\ldots+(-1)^{v-2}r^2+(-1)^{v-1}r+(-1)^v)=r^{v+1}-(-1)^{v+1}$$
Examples: $$\begin{align}(r+1)(r-1)=r^2-1\\(r+1)(r^2-r+1)=r^3+1\\(r+1)(r^3-r^2+r-1)=r^4-1\\(r+1)(r^4-r^3+r^2-r+1)=r^5+1\end{align}$$
Now substitute $r=2$ and you get immediately $3H_v=2^{v+1}-(-1)^{v+1}$ or $H_v=(2^{v+1}-(-1)^{v+1})/3$.
A: The equation you were staring at for hours 
$H_v=2^v - 2^{v-1} + 2^{v-2} - 2^{v-3} + ... + (-1)^{v-1}2 + (-1)^v$
can be simplified to
$2^{v-1} + 2^{v-3} + ... +1$ for $v$ odd  and $2^{v-1}+2^{v-3}+...+1$ for $v$ even 
=$\dfrac{2^{v-1}-\frac14}{1-\frac14}$ for $v$ odd and $\dfrac{2^{v-1}-\frac12}{1-{\frac14}}+1$ for $v$ even (using geometric series formula)
$=\dfrac{2^{v+1}-1}3$ for $v$ odd and $\dfrac{2^{v+1}+1}3$ for $v$ even
=$\dfrac{2^{v+1}+(-1)^v}3$
A: You can also get rid of the exponential term by changing variables: let $h_n=\frac{H_n}{2^n}$, so that $h_0=1$, and $h_n=1-\frac12h_{n-1}$ for $n\ge 1$. Then
$$\begin{align*}
h_n&=1-\frac12h_{n-1}\\
&=1-\frac12\left(1-\frac12h_{n-2}\right)\\
&=1-\frac12+\frac14h_{n-2}\\
&=1-\frac12+\frac14\left(1-\frac12h_{n-3}\right)\\
&=1-\frac12+\frac14-\frac18h_{n-3}\\
&\;\;\vdots\\
&=\sum_{i=0}^{k-1}\left(-\frac12\right)^i+\left(-\frac12\right)^kh_{n-k}\\
&\;\;\vdots\\
&=\sum_{i=0}^n\left(-\frac12\right)^i\\
&=\frac{1-\left(-\frac12\right)^{n+1}}{1-\left(-\frac12\right)}\\
&=\frac23\left(1-\frac{(-1)^{n+1}}{2^{n+1}}\right)\;,
\end{align*}$$
so
$$H_n=2^nh_n=\frac13\left(2^{n+1}-(-1)^{n+1}\right)=\frac13\left(2^{n+1}+(-1)^n\right)\;.$$
A: That one is a linear recurrence, first order, constant coefficients:
$\begin{align*}
  H_{v + 1} + H_v
    &= 2 \cdot 2^v
\end{align*}$
The summing factor here turns out to be $(-1)^{v + 1}$. Divide through by it:
$\begin{align*}
  \frac{H_{v + 1}}{(-1)^{v + 1}} - \frac{H_v}{(-1)^v}
    &= \frac{2 \cdot 2^v}{(-1)^{v + 1}} \\
  \sum_{0 \le k \le v - 1}
    \left(
      \frac{H_{k + 1}}{(-1)^{k + 1}} - \frac{H_k}{(-1)^k}
    \right)
    &= 2 \sum_{0 \le k \le v - 1} (-1)^{k + 1} 2^k \\
  \frac{H_v}{(-1)^v} - \frac{H_0}{(-1)^0}
    &= - 2 \sum_{0 \le k \le v - 1} (-1)^k 2^k \\
    &= - 2 \frac{1 - (-1)^v 2^v}{1 - 2} \\
    &= 2 (1 - (-1)^v 2^v) \\
  H_v
    &= (-1)^v (H_0 + 2 (1 - (-1)^v 2^v))
\end{align*}$
Quite ugly, true.
