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
When you make a cell phone call, which type of electromagnetic wave is most likely transmitting the signal?
Olegator [25]
They use Radio waves 
6 0
3 years ago
You work for a large company. You need to implement a backup solution for your company that will allow you to perform multiple b
Scrat [10]

Answer:

A Tape Library

Explanation:

A tape library, sometimes called a tape silo, tape robot or tape jukebox, is a storage device that contains one or more tape drives, a number of slots to hold tape cartridges, a barcode reader to identify tape cartridges and an automated method for loading tapes. It Enables faster data migrations, reduce the complexity of and increase the frequency of backups, and streamline governance in a secure and cost-effective way.

6 0
3 years ago
What are some ways to insert a row or column? Check all that apply.
kondaur [170]

Answer:

There are two ways to insert the new column or row in the table.

Explanation:

<u>Method I</u>

i. Select the cell where you want to add a new row or column,

ii. Click on Home Tab

iii. Find insert button in Cells Group.

iv. Click on Insert Row or Insert Column button.

By following above mentioned steps we can add a row or column in Excel sheet.

<u>Method II</u>

i. Select the cell where you want to add a new row or column,

ii. Right Click on the selected Cell.

iii. Find Insert Button in drop down menu and Click on Insert.

iv. There are four options in POP menu, choose Entire Row or Entire Column to insert row or column.

4 0
3 years ago
Read 2 more answers
Write an algorithm which gets a number A, if it is even, prints even, and if it is odd prints odd.
juin [17]

Answer:

The algorithm to find A is even or odd.

  1. input A.
  2. Check the remainder on diving by 2 by A%2.
  3. If remainder is 1 then A is odd Print(Odd).
  4. If remainder is 0 print(Even).

Explanation:

To check if the number is even or odd we use modulo  operator(%).Which gives the remainder on dividing.So if we do this A%2 it will give the remainder that will come out on dividing the value of A by 2.

So if the remainder comes out is 1 then the number is odd and if the remainder is 0 then the number is odd.

7 0
3 years ago
Which of the following statements isNOT true about abstract data types (ADTs)?A list is anexample of an ADT.ADTs hide theimpleme
Fynjy0 [20]

Answer:

Java provide all the ADTs you need,therefore you do not need to create any newones.

This statement is not true.

Explanation:

ADTs are those data types which we use but we didn't know their inner working that is how it is working what is happening inside.It is commonly used for Data Structures for example:- In stack we use push and pop operations to insert and to delete element from a stack respectively but we didn't know how it is happening inside.How the stack is implemented and etc.Java provides most of the ADT's but not all.

5 0
3 years ago
Other questions:
  • Waterpower was first harvested by ancient societies using
    5·1 answer
  • The very first thing I should type when creating a formula in excel is:
    15·2 answers
  • To use an imported image, simply drag it from the desktop onto the stage. true or false?
    14·1 answer
  • To print data sideways on a piece of paper, use the _______ page orientation setting.
    6·2 answers
  • Can someone help me, please
    7·1 answer
  • Search engines enable you to
    12·1 answer
  • ___________ is related to mass, but also includes the gravitational pull of the Earth.
    14·1 answer
  • According to the video, what kinds of projects would Computer Programmers be most likely to work on? Check all that apply.
    13·2 answers
  • Imagine you were going to use a dedicated workstation for an animation job rather than a personal PC or the all-purpose PCs you
    5·1 answer
  • Which tab is the "page break" command found on? (there are two!) *
    5·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!