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
Write a C program that creates two threads to run the Fibonacci and the Runner processes. Threads will indicate the start and th
OleMash [197]

Answer:

see explaination

Explanation:

#include <pthread.h>

#include <stdio.h>

int sumOfN = 0;

int arr[1000];

int n;

void * findSumOfN(void *a){

printf("Thread 1 Starting\n");

sumOfN = (n * (n+1)) / 2; //finds sum of first n natural numbers

printf("Thread 1 Finished\n");

pthread_exit(0);

}

void * fibonacci(void *a){

printf("Thread 2 Starting\n");

arr[0]=0;

arr[1]=1;

for(int i=2;i<n;i++) //find fibonacci numbers iteratively

arr[i]=arr[i-1]+arr[i-2];

printf("Thread 2 Finished\n");

pthread_exit(0);

}

int main(void){

printf("Please enter the value of n \n");

scanf("%d", &n);

if (n <= 0)

{

printf("Wrong input ! \n"); //input validation

return 0;

}

pthread_t thread1, thread2;

pthread_create(&thread1,NULL, findSumOfN, NULL); //Create threads

pthread_create(&thread2,NULL, fibonacci, NULL);

pthread_join(thread1,NULL); //Start threads

pthread_join(thread2, NULL);

printf("The sum of first %d numbers is : %d \n",n, sumOfN);

printf("The first %d fibonacci numbers are : \n",n);

for (int i = 0; i < n; ++i)

{

printf("%d ", arr[i]);

}

printf("\n");

return(0);

}

3 0
3 years ago
You want to set the sticky bit on an existing directory, subdir, without otherwise altering its permissions. to do so, you shoul
nikklg [1K]

If you want to set the sticky bit on an existing directory, subdir, without otherwise altering its permissions. to do so, you should type chmod a <u>t  <subdir>.</u>

<h3>What is Subdir?</h3>

The Definition of the term subdirectory is known to be a kind of an organizational directory that can be seen on a computer.

It is known to be one that can be found inside another directory  such as a subfolder. It is seen as the file a person is looking for and it is one that needs to have an extension.

Therefore, if you want to set the sticky bit on an existing directory, subdir, without otherwise altering its permissions. to do so, you should type chmod a <u>t  <subdir>.</u>

Learn more about directory from

brainly.com/question/14845522

#SPJ1

See full question below

You want to set the sticky bit on an existing directory, subdir, without otherwise altering its permissions. To do so, you should type:

chmod a+_____ <subdir>

- s

- p

- b

- t

6 0
2 years ago
Robert and Anne, a married couple filing jointly, have an adjusted gross income of $68,676. They claim two exemptions, and can d
artcher [175]

Answer:

the answer is B

Explanation:

Just took the test

8 0
2 years ago
Read 2 more answers
__________ requires unbiased and careful questioning of whether system elements are related in the most effective ways, consider
Liono4ka [1.6K]

Answer:

The answer is "Critical analysis".

Explanation:

Critical analysis is a part of the operating system, that provides an analysis, which is used to process all bits in a system and run their computer system more efficiently.

  • This analysis is used in contextual writing because It reflects the author's interpretation or perception of the text.
  • This analysis hosts vulnerabilities in current desktop operating systems objectively.
5 0
3 years ago
The third assignment involves writing a Python program to compute the cost of carpeting a room. Your program should prompt the u
mojhsa [17]

Answer:

# price of the carpet per square foot for each quality.

carpet_prices=[1,2,4]

def cal_cost(width,height,choice):

 return width*height*carpet_prices[choice-1]  

width=int(input("Enter Width : "))

height=int(input("Enter Height : "))

print("---Select Carpet Quality---")

print("1. Standard Quality")

print("2. Primium Quality")

print("3. Premium Plus Quality")

choice=int(input("Enter your choice : "))

print(f"Carpeting cost = {cal_cost(width,height,choice)}")

Explanation:

The cal_cost function is used to return the cost of carpeting. The function accepts three arguments, width, height, and the choice of carpet quality.

The program gets the values of the width, height and choice, calls the cal_cost function, and prints out the string format of the total carpeting cost.

3 0
3 years ago
Other questions:
  • The Cisco IOS automatically modifies the dead interval when the _____ interval is changed. (Points : 2) hello
    13·1 answer
  • All computers can support multiple internal hard drives. <br><br> a. True <br><br> b. False
    13·1 answer
  • Two-factor authentication can best be breached by the adversary using:________. a. social engineering attack b. using sniffers l
    10·1 answer
  • Which port must be open on your router to allow you to upload device configuration and firmware updates using trivial file trans
    13·1 answer
  • How can you say that a painting is real? ​
    7·2 answers
  • A student is browsing a website. While browsing, he click on a link that takes him to another website. Which code gives the corr
    14·1 answer
  • Hi, I am from India. Our brainly platform isn't so good, many of 'em keep spamming questions that I ask. US platform seems much
    9·1 answer
  • Rebbeca has finished with the research and outline portion of her slide presentation. Now, the next logical step is to begin wor
    11·1 answer
  • What is a man-in-the-middle attack​
    14·2 answers
  • ________ helps in determining the cause of a security threat in an incident response plan. Question 7 options: A) Restricting sy
    5·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!