Please use induction Consider the following code fragment: int i -1; int s=1; while (i <-...

Question

Question

Consider the following code fragment: int i -1; int s=1; while (i <- n) Show that at the start of every iteration holds using induction

Please use induction

Answer 1

Answer #1

F(1) = 1*1 = 1 base case is true s=1 //

let F(i) is true

F(i) = S+2*i+1 = i*i

then F(i+1) must be true // induction step

F(i+1) = F(i) + 2*i+1

-> i*i +2*i+1

-> i*i+ i+i+1

->i*(i+1) +(i+1)

->(i+1)*(i+1)

-> (i+1)²

F(i+1) is also true when F(i) is true

hence induction holds

Add a comment

Answer 2

Similar Homework Help Questions

What is the output of the following code fragment? int i = 1; while( i <=...

What is the output of the following code fragment? int i = 1; while( i <= 5 ) if(i == 2 || i == 4) System.out.println(i + ":" + " is an even index) System.out.println("i: " + i); i++;
Using C++ please explain What is the Big-O time complexity of the following code: for (int...

Using C++ please explain What is the Big-O time complexity of the following code: for (int i=0; i<N; i+=2) { ... constant time operations... Select one: o a. O(n^2) O b. O(log n) c. O(n) O d. 0(1) What is the Big-O time complexity of the following code: for(int i=1; i<N; i*=2) { ... constant time operations... Select one: O O a. O(n^2) b. 0(1) c. O(n) d. O(log n) O What is the Big-O time complexity of the following...
What is the output of the following code? for(int i =0; i<3; i++) { int x...

What is the output of the following code? for(int i =0; i<3; i++) { int x = 0; x = x+i; Sy System.out.println(x);

C++ READ CODE: 8. Below is a code fragment; assume x is an integer with the...

C++ READ CODE: 8. Below is a code fragment; assume x is an integer with the value 40 at the start of the code fragment. Execute each code fragment and show the output below that code fragment. if (x 25) if (x 0) x=x*2; x=x+1; else ( x1i cout < xi
Consider the following code. It is valid. What is printed? public static void TestLabel() { int...

Consider the following code. It is valid. What is printed? public static void TestLabel() { int i = 0; MyLabel: for (i++; i<20; i++) { if (i 10) continue MyLabel; System.out.println(i); } nothing (doesn't work) 20 10
Consider the following C++ code segment: for (int i = 0; i <n; ++i) { for...

Consider the following C++ code segment: for (int i = 0; i <n; ++i) { for (int j = 0; j <m; ++j) if (i != j) cout << "0"; else cout << "1"; } } Which of the options below gives the correct output if the value of nis 2and the value of mis 3? 1. 100010 2. 011101 3. 100100 4. 010001

I don’t understand can you help 5. Given the definition and code fragment: (2 points int...

I don’t understand can you help 5. Given the definition and code fragment: (2 points int matrix[2]13]; int k = 0; for(int i =0; i < 2; i++) for (int j=0, j < 3 ) matrix[i]lj]-k++; The value of matrix[1][1] is
A. What is the output of the following C++ code fragment? (all variables are of type...

A. What is the output of the following C++ code fragment? (all variables are of type int) int count-1; int y-100; while (count 3) y=y-1 ; count+t cout << y << endl; cout<< count <<endl What is the value of x after control leaves the following while loop? (all variables are of type int) B. int x0 while (x < 20) sum- sum+x cout << sum<< endl;
What is the time complexity of the following code segment? for (int i = 0; i<n;...

What is the time complexity of the following code segment? for (int i = 0; i<n; i--) if (a[i] != 0) sum = a[i]; What is the time complexity of the following code segment? for (int i = 0; i<10; i++) if (a[i] != 0) sum += a[i]; What is the time complexity of the following code segment? for (int i = 0; i<n/2; i++) if (a[i] != 0) sum += a[i]; What is the time complexity of the following...

Compile the following C while loop into MIPS assembly code assuming the following register-variable mapping shown...

Compile the following C while loop into MIPS assembly code assuming the following register-variable mapping shown below. Also assume the array A holds integers.//$s0: A, $s1: I, $s2: j, $s3: x for(i=0; i<100; i++) {x=0; for(j = i + l; j < 100; j++) {x = x + A [j];} A[i] = x;}