Proof by Mathematical Induction

needmathhelp1
Messages
2
Reaction score
0
I am confused on a math problem. I am supposed to use mathematical induction to show that

(Summation with n on top and i=1 on the bottom) (2i-1) = 1+3+5+...+(2n-1)= n^2
 
Physics news on Phys.org
We are given to prove:

$$S_n=\sum_{i=1}^n(2i-1)=n^2$$

Step 1: demonstrate the base case is true.

$$S_1=\sum_{i=1}^1(2i-1)1=1^2$$

This is true.

Step 2: State the induction hypothesis $P_k$:

$$S_k=\sum_{i=1}^k(2i-1)=k^2$$

Step 3: Make the inductive step, and obtain $P_{k+1}$.

What do you get if you add $2k+1$ to both sides?
 
MarkFL said:
We are given to prove:

$$S_n=\sum_{i=1}^n(2i-1)=n^2$$

Step 1: demonstrate the base case is true.

$$S_1=\sum_{i=1}^1(2i-1)1=1^2$$

This is true.

Step 2: State the induction hypothesis $P_k$:

$$S_k=\sum_{i=1}^k(2i-1)=k^2$$

Step 3: Make the inductive step, and obtain $P_{k+1}$.

What do you get if you add $2k+1$ to both sides?

I understand the first two steps, but I am not sure what the inductive step is or how to obtain $P_{k+1}$.
 
The inductive step is essentially a legal algebraic operation you perform on $P_k$ that leads to $P_{k+1}$, usually after some simplification.

If you use the step I suggested, you then have:

$$\sum_{i=1}^k(2i-1)+2k+1=k^2+2k+1$$

Can you incorporate the added terms into the sum on the left and factor the right?
 
Since several days has gone by with no feedback from the OP, I will finish. We have:

$$\sum_{i=1}^k(2i-1)+2k+1=k^2+2k+1$$

On the left side, rewrite the added terms so that they are in the form of the summand:

$$\sum_{i=1}^k(2i-1)+2(k+1)-1=k^2+2k+1$$

Incorporate these terms into the sum and factor the right side as a square:

$$\sum_{i=1}^{k+1}(2i-1)=(k+1)^2$$

We have now derived $P_{k+1}$ from $P_k$, thereby completing the proof by induction.
 
Hi all, I've been a roulette player for more than 10 years (although I took time off here and there) and it's only now that I'm trying to understand the physics of the game. Basically my strategy in roulette is to divide the wheel roughly into two halves (let's call them A and B). My theory is that in roulette there will invariably be variance. In other words, if A comes up 5 times in a row, B will be due to come up soon. However I have been proven wrong many times, and I have seen some...
Thread 'Detail of Diagonalization Lemma'
The following is more or less taken from page 6 of C. Smorynski's "Self-Reference and Modal Logic". (Springer, 1985) (I couldn't get raised brackets to indicate codification (Gödel numbering), so I use a box. The overline is assigning a name. The detail I would like clarification on is in the second step in the last line, where we have an m-overlined, and we substitute the expression for m. Are we saying that the name of a coded term is the same as the coded term? Thanks in advance.

Similar threads

Replies
8
Views
2K
Replies
4
Views
2K
Replies
5
Views
4K
Replies
5
Views
2K
Replies
6
Views
2K
Replies
4
Views
1K
Back
Top