1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Alekssandra [29.7K]
3 years ago
14

Recursively computing the sum of the first n positive odd integers, cont. About (a) Use induction to prove that your algorithm t

o compute the sum of the first n positive odd integers returns the correct value for every positive integer input.
Computers and Technology
1 answer:
julia-pushkina [17]3 years ago
6 0

The recursive function would work like this: the n-th odd number is 2n-1. With each iteration, we return the sum of 2n-1 and the sum of the first n-1 odd numbers. The break case is when we have the sum of the first odd number, which is 1, and we return 1.

int recursiveOddSum(int n) {

 if(2n-1==1) return 1;

 return (2n-1) + recursiveOddSum(n-1);

}

To prove the correctness of this algorithm by induction, we start from the base case as usual:

f(1)=1

by definition of the break case, and 1 is indeed the sum of the first odd number (it is a degenerate sum of only one term).

Now we can assume that f(n-1) returns indeed the sum of the first n-1 odd numbers, and we have to proof that f(n) returns the sum of the first n odd numbers. By the recursive logic, we have

f(n)=f(n-1)+2n-1

and by induction, f(n-1) is the sum of the first n-1 odd numbers, and 2n-1 is the n-th odd number. So, f(n) is the sum of the first n odd numbers, as required:

f(n)=\underbrace{\underbrace{f(n-1)}_{\text{sum of the first n-1 odds}}+\underbrace{2n-1}_{\text{n-th odd}}}_{\text{sum of the first n odds.}}

You might be interested in
Question Mode Matching Question Match the following description with the appropriate programming language generation. 1GL 1GL dr
erastovalidia [21]

Answer:

1GL: Machine language. Represented by a series of 1s and 0s.

2GL: Assembly language. An assembler converts 2GL into machine language.

3GL: High-level programming language. Uses a compiler to convert into machine language.

4GL: Specifically designed for creating database management programs.

5GL: Extremely advanced. Uses statements (scripts) rather than algorithms.

Explanation:

Programming languages started as a series of binary digits (i.e. 0's and 1'). This generation of language is referred to as the first generation.

However, the machine language were difficult to read by human, so mnemonics were created (i.e. assembly language). This language uses symbolic codes such as ADD for addition, etc. This is the second generation

The third generation are the high level languages that uses languages that can be easily understood by human, e.g. + means plus. However, the language must be translated; hence the need for a compiler or interpreter, as the case may be.

The fourth and fifth generations are extensions of the third generation languages. The fourth were created to connect to DBMS while the fifth are more advanced.

4 0
3 years ago
I’m so lost. which username do i do.
koban [17]

Answer:

the username you feel like using

5 0
2 years ago
Read 2 more answers
Application software developed by the user or at the user’s request is called ____ software.
Zolol [24]
End-User Software. Because it is not professional

4 0
3 years ago
A __________ search engine focuses on a specific subject.<br><br>answer : Specialized
natita [175]

Answer:

Specialized fr just want point lol

Explanation:

5 0
2 years ago
Four categories of installer apps
Naddika [18.5K]

Answer:

I find 5 categories

Explanation:

1 Overview

2 Necessity

3 Types

4 Attended installation

4.1 Silent installation

4.2 Unattended installation

4.3 Headless installation

4.4 Scheduled or automated installation

4.5 Clean installation

4.6 Network installation

5 Installer

5.1 Bootstrapper

5.2 Common types

5.3 System installer

7 0
3 years ago
Other questions:
  • The border that defines the outer boundary of a shape or other object
    13·1 answer
  • How to track flash socket server connections wireshark?
    10·1 answer
  • 2-Write test programs in java to determine the scope of a variable declared in a for statement. Specifically, the code must dete
    7·1 answer
  • What is the fundamental problem producers and consumers face?
    12·1 answer
  • When you start to type =av, what feature displays a list of functions and defined names?
    11·1 answer
  • Imagine your friend wants to apply
    5·1 answer
  • Run a Monte Carlo simulation on this vector representing the countries of the 8 runners in this race: runners &lt;- c("Jamaica",
    14·1 answer
  • To implement a small database, a database designer must know the "1" and the "M" sides of each relationship and whether the rela
    7·1 answer
  • Which of the following is considered a modern method of communication?
    7·2 answers
  • 45 points!
    9·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!