Recurrence Relation: Hᵥ = 2ᵛ - Hᵥ₋₁

Question

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.

Answer 1

$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$

Answer 2

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.

Answer 3

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$.

Answer 4

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$

Answer 5

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)\;.$$