How to add 'n' amount of odd integers?

Question

I'm trying to write a program that computes the sum of the first n positive odd integers.

I'm having trouble figuring out how to incorporate n into finding the sum. I already have a do/while loop to ensure I get a positive value when assigning n value. I know that I have to use a for loop but I'm not really sure how I would do that.

Scanner input = new Scanner(System.in); // open input stream
    String cleanUpStr;                      // clean kbd buffer
    int n;                                  // number
    int sum;                                // sum of numbers
    int cntr;                               // counter for loop

    cleanUpStr = "nothing yet";
    n = 0;
    sum = 0;
    cntr = 0;

    //prompt user for the value of n
    // use a loop to ensure a positive output
    do
    {
        System.out.println("Enter the value of n");

        n = input.nextInt();
        cleanUpStr = input.nextLine();

        // print error if n is invalid
        if (n < 0)
        {
            System.out.println("Invalid n value of " + n + ", try again.");
        } // end if

    }while(n < 0);

    for(cntr = 0; cntr < n; ++cntr)
    {


    } // end for




} // end main

For example: if n = 5, then this should compute 1 + 3 + 5 + 7 + 9.

Answer 1

The nice thing about this problem, is that you don't need to write a loop! The sum of the first n positive odd integers is the square of n (written throughout this post as n^2). This is how you express the sum in terms of n. So the following will suffice:

// Calculate the sum of first n positive odd integers by using the n^2 formula.
public static int sumOddIntegers(int n) {
    return n*n;
}

If you're set on using a loop, you can do the following by observing that the i-th positive odd integer can be calculated using the formula (2i-1):

// Calculate the sum of first n positive odd integers by adding each number iteratively in a loop.
public static int sumOddIntegers(int n) {
    int oddSum = 0;
    for (int i = 1; i <= n; i++) {
        oddSum += (2*i - 1);
    }
    return oddSum;
}

To visualize this, consider the following examples:

n = 1 List: {1} S(n) = 1 = 1 = n^2
n = 2 List: {1, 3} S(n) = 1 + 3 = 4 = n^2
n = 3 List: {1, 3, 5} S(n) = 1 + 3 + 5 = 9 = n^2
n = 4 List: {1, 3, 5, 7} S(n) = 1 + 3 + 5 + 7 = 16 = n^2
n = 5 List: {1, 3, 5, 7, 9} S(n) = 1 + 3 + 5 + 7 + 9 = 25 = n^2
And so on...

Here is a proof by induction showing that the sum of the first n positive odd numbers is n^2. I'm new to Stack Overflow, so I hope my formatting is legible. If it can be improved, please feel free to suggest edits :) It seems like Stack Overflow doesn't support LaTeX style exponent and subscript formatting, so I did my best.

Proof

P(n): The sum of the first n positive odd integers is n^2.

Base Case

P(1): n = 1

The n = 1 case is trivial. The list of the first n positive odd integers is simply {1}. Therefore the sum of the first n positive odd integers is 1. Since 1 = n = n^2, the predicate P(1) holds true.

Inductive Hypothesis

Assume that P(k) holds for any arbitrary positive integer k > 0.

Inductive Step

Given P(k), we will prove that P(k+1) also holds true. In words, if the sum of the first k positive odd integers is k^2, then the sum of the first (k+1) positive odd integers is (k+1)^2.

As part of this proof, assume the following lemma.

Lemma 1: The nth positive odd integer can be expressed as 2n-1.

If P(k) holds, then the sum of the first k positive odd integers {a_1, ... a_k} is k^2 where the element a_k is expressed as 2k-1 (by Lemma 1). It follows that adding the (k+1)st positive odd integer, a_(k+1) to the list of the first k positive odd integers will produce a list of the first (k+1) positive odd integers as follows: {a_1, ... a_k, a_(k+1)}. Therefore, the sum of this list of the first (k+1) positive odd integers will be equal to the sum of the list of the first k positive odd integers plus the value of a_(k+1), the (k+1)st positive odd integer. By Lemma 1, the (k+1)st positive odd integer is expressed as 2(k+1)-1 = 2k+1.

Let S(k) = the sum of the first k positive odd integers. Therefore, S(k) = k^2. The above statements imply that

S(k+1) = S(k) + a_(k+1), adding the (k+1)st positive odd integer

S(k+1) = S(k) + (2(k+1)-1), by Lemma 1 

S(k+1) = S(k) + (2k+1)  

S(k+1) = k^2 + (2k+1), by inductive hypothesis

S(k+1) = k^2 + 2k + 1

S(k+1) = (k+1)^2, by factoring

We have therefore shown that if S(k) = k^2, then S(k+1) = (k+1)^2. This shows that P(k) -> P(k+1).

By induction, we have proved that P(n) holds for any positive integer n > 0. The sum of the first n positive odd integers is therefore n^2. QED.

Proof of Lemma 1:

Here is a proof of this by induction.

P(n): The nth positive odd integer, a_n, can be expressed as 2n-1.

Base case: P(1): 1 is the first positive odd integer (case n = 1).

1 = 2(1)-1 = 1. 

Therefore, a_1 = 1 = 2n-1. Correct.

Inductive Hypothesis: Assume P(k) holds.

Inductive Step: If P(k) holds, then P(k+1) holds.

If P(k) holds, then the kth positive odd integer can be expressed as 2k-1. By addition, the next positive odd integer (the (k+1)st positive odd integer), would be (2k-1) + 2.

= (2k-1) + 2
= 2k-1 + 2
= 2k+2 - 1
= 2(k+1) -1

We have shown that P(k) -> P(k+1). Therefore, by induction, P(n) holds for all integers n > 0. QED.

Good luck! Hope this was helpful :)