I can't manage to prove the given identity by induction in the document i placed here. I manage to do this kind of proof when there is only k on the left qide and n on the right side, but now there is both n and k on the left side. Can anyone help me with it ?
You are using an out of date browser. It may not display this or other websites correctly.
You should upgrade or use an alternative browser.
You should upgrade or use an alternative browser.
Unclear induction proof
- Thread starter Nico55
- Start date
HallsofIvy
Elite Member
- Joined
- Jan 27, 2012
- Messages
- 7,763
The problem is to prove, by induction, that \(\displaystyle \sum_{k= 1}^n (-1)^{n- k}k^2= \frac{n(n+1)}{2}\).
You say "now there is both n and k on the left side". I presume you mean the n in "\(\displaystyle (-1)^{n- k}\)" not the sum "to n" since that is commonly there. Surely you know, by simple algebra, that \(\displaystyle (-1)^{n-k}= (-1)^n(-1)^{-k}\) and then we can factor \(\displaystyle (-1)^n\) out of the sum. Further, since \(\displaystyle \frac{1}{-1}= -1\), \(\displaystyle (-1)^{-k}= (-1)^k\).
The problem is to prove, by induction, that \(\displaystyle (-1)^n\sum_{k= 1}^n (-1)^k k^2= \frac{n(n+1)}{2}\).
Now, induction should be obvious. The "base case" is n= 1 and in that case, the left side is just \(\displaystyle (-1)(-1)(1^2)= 1\) and the right side is \(\displaystyle \frac{1(1+1)}{2}= 1\).
Since this is a sum, the "n+1" case is just the sum up to n, the "n" case with one additional term:
\(\displaystyle (-1)^n\sum_{k=1}^n (-1)^k k^2+ (-1)^{n+1}(-1)^{n+1} (n+1)^2\)
Since the "induction hypothesis" is that the sum in that last is \(\displaystyle \frac{n(n+1)}{2}\), this reduce to showing that \(\displaystyle \frac{n(n+1)}{2}+ (n+1)^2= \frac{(n+1)(n+2)}{2}\).
(I have used the obvious fact that \(\displaystyle (-1)^{n+1}(-1)^{n+1}= 1\).)
You say "now there is both n and k on the left side". I presume you mean the n in "\(\displaystyle (-1)^{n- k}\)" not the sum "to n" since that is commonly there. Surely you know, by simple algebra, that \(\displaystyle (-1)^{n-k}= (-1)^n(-1)^{-k}\) and then we can factor \(\displaystyle (-1)^n\) out of the sum. Further, since \(\displaystyle \frac{1}{-1}= -1\), \(\displaystyle (-1)^{-k}= (-1)^k\).
The problem is to prove, by induction, that \(\displaystyle (-1)^n\sum_{k= 1}^n (-1)^k k^2= \frac{n(n+1)}{2}\).
Now, induction should be obvious. The "base case" is n= 1 and in that case, the left side is just \(\displaystyle (-1)(-1)(1^2)= 1\) and the right side is \(\displaystyle \frac{1(1+1)}{2}= 1\).
Since this is a sum, the "n+1" case is just the sum up to n, the "n" case with one additional term:
\(\displaystyle (-1)^n\sum_{k=1}^n (-1)^k k^2+ (-1)^{n+1}(-1)^{n+1} (n+1)^2\)
Since the "induction hypothesis" is that the sum in that last is \(\displaystyle \frac{n(n+1)}{2}\), this reduce to showing that \(\displaystyle \frac{n(n+1)}{2}+ (n+1)^2= \frac{(n+1)(n+2)}{2}\).
(I have used the obvious fact that \(\displaystyle (-1)^{n+1}(-1)^{n+1}= 1\).)
The problem is to prove, by induction, that \(\displaystyle \sum_{k= 1}^n (-1)^{n- k}k^2= \frac{n(n+1)}{2}\).
You say "now there is both n and k on the left side". I presume you mean the n in "\(\displaystyle (-1)^{n- k}\)" not the sum "to n" since that is commonly there. Surely you know, by simple algebra, that \(\displaystyle (-1)^{n-k}= (-1)^n(-1)^{-k}\) and then we can factor \(\displaystyle (-1)^n\) out of the sum. Further, since \(\displaystyle \frac{1}{-1}= -1\), \(\displaystyle (-1)^{-k}= (-1)^k\).
The problem is to prove, by induction, that \(\displaystyle (-1)^n\sum_{k= 1}^n (-1)^k k^2= \frac{n(n+1)}{2}\).
Now, induction should be obvious. The "base case" is n= 1 and in that case, the left side is just \(\displaystyle (-1)(-1)(1^2)= 1\) and the right side is \(\displaystyle \frac{1(1+1)}{2}= 1\).
Since this is a sum, the "n+1" case is just the sum up to n, the "n" case with one additional term:
\(\displaystyle (-1)^n\sum_{k=1}^n (-1)^k k^2+ (-1)^{n+1}(-1)^{n+1} (n+1)^2\)
Since the "induction hypothesis" is that the sum in that last is \(\displaystyle \frac{n(n+1)}{2}\), this reduce to showing that \(\displaystyle \frac{n(n+1)}{2}+ (n+1)^2= \frac{(n+1)(n+2)}{2}\).
(I have used the obvious fact that \(\displaystyle (-1)^{n+1}(-1)^{n+1}= 1\).)
Thanks! Just one thing, maybe it is a stupid question, but why am I allowed to separate (-1)^n to the outside of the sum ? Because for even n I will get 1, for uneven n I will get -1, so wouldn't that give different results based on the n you'd use ?