Chapter Review: #6 Please write neat Select all true statements. Induction is a
ID: 3778050 • Letter: C
Question
Chapter Review: #6 Please write neat
Select all true statements. Induction is a special case of structural induction. The Fibonacci sequence/, is big-Omega of (3/2)^n. In a structural induction proof, to show that a statement P(n) holds for all elements n of a recursively defined set, you must show P(n) for all n in the initial population, and that whenever P(n) is true for some n, P(n+1) is also true. In a structural induction proof, to show that a statement holds for all elements of a recursively defined set, you must show it for all members of the initial population, and that it is passed on through the recurrence relations that create new elements from old elements. If P(n) is a statement that is false for some, or even all, natural numbers n, it is still possible that P(n) rightarrow P(n + 1) holds for all natural numbers n. In an inductive proof, you always obtain the statement P(n+1) by adding n to both sides of P(n). You can prove a statement P(n) for all natural numbers n by showing P(1) and P(n) rightarrow P{n + 1) for all natural numbers n. You prove a statement P(n) by induction for all natural numbers n by showing P(1) and by showing that if P(k) is true for all natural numbers k, then P(k+1) must also be true. You can prove a statement P(n) for all natural numbers n by showing P(1), P(2) and P(n) rightarrow P(n + 1) for all natural numbers n. The rules that create new from old elements in a recursively defined set never create the same element twice.Explanation / Answer
A) TRUE
Structural induction is a special case of Noetherian induction( mathematical induction). But they are not same.
----------------------------------------------------------------------------------------------------------------------
B) FALSE
Here at every step it will recall function itsef.
So T(n-1) = O(2^n-1)
==> T(n) = O(2^n-1) + O(2^n-2) + O(1) ==> O(2^n)
-----------------------------------------------------------------------------------------------------
C) FALSE
It passes through the recurrrence relations that create new elements from old elements.
---------------------------------------------------------------------------------------------------
D) TRUE
It passes through the recurrrence relations that create new elements from old elements.
------------------------------------------------------------------------------------------------------
E)FALSE
For all natural numbers P(n) is false , So P(n+1) also false.
---------------------------------------------------------------------------------------------------
F)TRUE
Adding both sides is to prove that for particular condition both LHS and RHS support.
-------------------------------------------------------------------------------------------
G)TRUE
That is actual procedure to prove statement using mathematical induction.
-------------------------------------------------------------------------------------------------
H) TRUE
Direct statement, explanation not required.
----------------------------------------------------------------------------------------------------
I)TRUE
This is the statement used for proving by mathematical induction.
------------------------------------------------------------------------------------------
J)FALSE
There might be chance that when deriving same element can occur. But it is special condition.