I have the given Recurrence Equation
$T:$ $\mathbb{N}$$_>$$_0$ $\rightarrow$ $\mathbb{Z}$
$$T(1) = 0$$
$$T(n) = T(n-1) + (-1)^n \cdot n,\ for\ n \in \mathbb{N} _>{_1}$$
What i tried is to just insert a few numbers for $n$ and i got *
$T(2) = 2 \\T(3) = -1 \\ T(4) = 3 \\ T(5) = -2 \\$
so it seems like i get the closed form $T(n) = n+1 \ for \ even \ n \ \\T(n) = 1\ - n \ for \ odd \ n$ $ \ $ so $ \ $ $ T(2n) = n + 1 \ \ \ \\ T(2n-1) = 1 -n$ right?
if i insert some $n$ now to verify it i get for example for $n=1$ the equation $T(2\cdot1) = 1+1 = 2 $ or for $n = 2$ the equation $T(2\cdot2) = 2 + 1 = 3$ so it seems correct to me for the even numbers, did the same for the odd numbers and got for $n = 1$ the equation $T(2\cdot1 -1) = 1- 1 = 0$ or for $n=2$ the equation $ T(2\cdot 2-1) = 1- 2 = -1$ both seem to match the values from above *
So i tried to proof now both seperatly by Induction for the even numbers
Induction Base Case: $ n=1 $ so i get $ T(2\cdot1) = 1+1 = 2 $
Induction Hypothesis: $T(2n) = n+1$ is true for one $n \in \mathbb{N}_>{_0} $
Induction Step, and this is where im stuck i tried to show that $ T(2\cdot (n+1)) = (n+1)+1 $ but it
seems like im doing something stupidly wrong im kinda new to that it is my 2nd Semester, if someone could explain me what im doing wrong here it would help me a lot. The Task is basically to find a Closed form for the Recurrence Equation above and proof it by Induction, everything else i wrote is what i tried so far.
2026-03-25 17:52:05.1774461125
On
From recurrence equation to closed proof by induction
147 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
2
There are 2 best solutions below
0
On
Thank you guys, i think i understand it now, i made also the induction for the odd $n$ if someone could just confirm that i made it correct:
Induction base: $n = 1$
$T(2\cdot 1-1) = T(1) = 0 = 1- 1$
Induction Hypothesis: $T(2n-1) = 1 - n $ is true for one $n \in \mathbb{N} _>{_0}$
Induction Step: $n = n+1$
[Have to show that $T(2(n+1) -1) = 1-(n+1) = -n$]
$T(2(n+1)-1) = T(2n+1) = T(2n) +(-1)^{2n+1} \cdot (2n+1)$
= $T(2n-1) +(-1)^{2n} \cdot 2n +(-1)^{2n+1} \cdot (2n+1)$ $ = 1-n+2n -2n -1 = -n$
$$ T(2(n+1))=T(2n+2)=T(2n+1)+(-1)^{2n+2}(2n+2)=T(2n)+(-1)^{2n+1}(2n+1)+(-1)^{2n+2}(2n+2)$$ Now note that $(-1)^{2n+1}=-1$ and $(-1)^{2n+2}=1$.