- #1
Proof by induction? No Idea what I should do :(
In summary, to find the general rule and prove by induction, we use the formula \sum_{n = 1}^k (-1)^{n - 1} n^2 = (-1)^{k + 1} \sum_{n = 1}^k n and the fact that \sum_{n = 1}^k n = \frac12k(k+1) to prove that \sum_{n = 1}^k (-1)^{n - 1} n^2 = \frac12(-1)^{k + 1}k(k+1). Then, by adding the extra term $(-1)^k(k+1)^2$ to
- #2
Opalg
Gold Member
MHB
- 2,778
- 13
You have the correct formula, except that $n^n$ should be $n^2$. I think your next step should be to simplify the right side of the formula by using the formula (which you probably know?) for the sum of the numbers $1$ to $n$. After that, you should be able to apply the method of induction.FriendlyCashew said:
- #3
- 2,019
- 825
Actually, I think what you want isFriendlyCashew said:
\(\displaystyle \sum_{n = 1}^k (-1)^{n - 1} n^2 = (-1)^{k + 1} \sum_{n = 1}^k n\)
Does this work for some value of k? (Sure, try k = 1.) So if it works for k, does it work for k + 1?
-Dan
- #4
FriendlyCashew
- 2
- 0
Is this correct?
- #5
Opalg
Gold Member
MHB
- 2,778
- 13
The equation that you are trying to prove by induction is \(\displaystyle \sum_{n = 1}^k (-1)^{n - 1} n^2 = (-1)^{k + 1} \sum_{n = 1}^k n\). Your first attempt at this was wrong, and so was mine (sorry about that). But topsquark got it right. The next step is to use the fact that \(\displaystyle \sum_{n = 1}^k n = \frac12k(k+1)\). So you want to prove that \(\displaystyle \sum_{n = 1}^k (-1)^{n - 1} n^2 = \frac12(-1)^{k + 1}k(k+1)\). That equation is true when $k=1$ because both sides are then equal to $1$.FriendlyCashew said:
Now suppose that the equation is true for $k$. You want to show that it is also true for $k+1$, namely that \(\displaystyle \sum_{n = 1}^{k+1} (-1)^{n - 1} n^2 = \frac12(-1)^{k + 2}(k+1)(k+2)\). On the left side of the equation, that differs from the previous equation just by the addition of one extra term $(-1)^k(k+1)^2$. So starting with the known equation \(\displaystyle \sum_{n = 1}^k (-1)^{n - 1} n^2 = \frac12(-1)^{k + 1}k(k+1)\), add $(-1)^k(k+1)^2$ to each side to get \(\displaystyle \sum_{n = 1}^{k+1} (-1)^{n - 1} n^2 = \frac12(-1)^{k + 1}k(k+1) + (-1)^k(k+1)^2\).
Now can you simplify the right side of that equation to complete the proof?
FAQ: Proof by induction? No Idea what I should do :(
What is proof by induction?
Proof by induction is a mathematical method used to prove that a statement is true for all natural numbers. It involves two steps: the base case, where the statement is shown to be true for the first natural number, and the inductive step, where it is shown that if the statement is true for one natural number, it is also true for the next natural number.
When is proof by induction used?
Proof by induction is typically used to prove statements about natural numbers, such as properties of sequences, series, and recursive definitions. It is also commonly used in computer science to prove the correctness of algorithms and programs.
What is the difference between strong and weak induction?
Strong induction and weak induction are two variations of proof by induction. In strong induction, the inductive step assumes that the statement is true for all previous natural numbers, while in weak induction, the inductive step only assumes that the statement is true for the previous natural number. Strong induction is more powerful and can be used in more complex proofs, but weak induction is simpler and easier to understand.
What is the principle of mathematical induction?
The principle of mathematical induction is the foundation of proof by induction. It states that if a statement is true for the first natural number, and if the truth of the statement for any given natural number implies its truth for the next natural number, then the statement is true for all natural numbers.
What are some common mistakes when using proof by induction?
One common mistake when using proof by induction is assuming that the statement is true for all natural numbers without properly proving it for the base case. Another mistake is incorrectly assuming that the inductive step is true for all previous natural numbers, when in fact it may only be true for the previous natural number. It is important to carefully follow the steps of proof by induction and provide clear and logical reasoning for each step.