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
Elizabeth works for a local restaurant at the end of her shift she read she’s required to write in the time that she arrived in
gavmur [86]
B - because you should always be honest when it comes to working your hours and getting paid the right amount.
5 0
3 years ago
To show the navigation pane if it is hidden, click the ____ button
Tcecarenko [31]
Hi,

I believe it's "show".

"To show the navigation pane if it's hidden,
click the show button"


Hope this helps.
r3t40
4 0
3 years ago
Read 2 more answers
HELPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP!!!
Bingel [31]

Answer:

different or difference between Dot-matrix and Daisy-wheel printer

3 0
3 years ago
In order to organize your work effectively on the computer, where is the best place to save it?
Morgarella [4.7K]
Your answer is -

B. Folder Is the best place to save it
8 0
3 years ago
Read 2 more answers
Allowing every communication is a bad idea from a security standpoint as well as a productivity one.TrueFalse
s344n2d4d5 [400]

Answer:

The answer to this question is True.

Explanation:

If we allow every communication this will not be a great idea if we want better security and better productivity.

There will be a lot of spam communications so the productivity and the security will also degrade because of that.

So if we want better productivity and security we have to allow a certain number of connections.

Hence the answer to this question is True.

4 0
3 years ago
Other questions:
  • Open source software is copyrighted software that is distributed at no cost for a trial period.
    11·1 answer
  • _____ is defined as an attraction for a source based on a resemblance between the source and receiver of a message.
    15·1 answer
  • What was the first fully computer animated feature film?
    13·1 answer
  • How many Iron molecules are in the compound Fe4O2?
    15·2 answers
  • Good ways to increase sales on phone accesories?
    10·2 answers
  • Which famous individuals was born on october 31st?
    7·1 answer
  • I connected to an external hard drive to transfer some photos from my vacation. When I try to drag the photo, it bounces right b
    14·1 answer
  • What are examples of Table Tools options that can help edit data?
    15·2 answers
  • Complete the function favoriteFlower(). Note that the program will not run as is because the function is incomplete. The purpose
    15·1 answer
  • Which of the following items in the folder window allows users to view locations which have been visited before?
    6·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!