sructural induction in rosen's book=

To prove results about recursively defined sets, we generally use some form of mathematical induction. Example 1 illustrates the connection between recursively defined sets and mathematical induction.

EXAMPLE 1

Show that the set S defined in Example 5 by specifying that 3 ∈ S and that if x ∈ S and y ∈ S, then x + y ∈ S, is the set of all positive integers that are multiples of 3. Solution: Let A be the set of all positive integers divisible by 3. To prove that A = S, we must show that A is a subset of S and that S is a subset of A. To prove that A is a subset of S, we must show that every positive integer divisible by 3 is in S.We will use mathematical induction to prove this. Let P(n) be the statement that 3n belongs to S. The basis step holds because by the first part of the recursive definition of S, 3 · 1 = 3 is in S. To establish the inductive step, assume that P(k) is true, namely, that 3k is in S. Because 3k is in S and because 3 is in S, it follows from the second part of the recursive definition of S that 3k + 3 = 3(k + 1) is also in S. To prove that S is a subset of A, we use the recursive definition of S. First, the basis step of the definition specifies that 3 is in S. Because 3 = 3 · 1, all elements specified to be in S in this step are divisible by 3 and are therefore in A. To finish the proof, we must show that all integers in S generated using the second part of the recursive definition are in A. This consists of showing that x + y is in A whenever x and y are elements of S also assumed to be in A. Now if x and y are both in A, it follows that 3 | x and 3 | y. By part (i) of Theorem 1 of Section 4.1, it follows that 3 | x + y, completing the proof. ▲ In Example 1 we used mathematical induction over the set of positive integers and a recursive definition to prove a result about a recursively defined set. However, instead of using mathematical induction directly to prove results about recursively defined sets, we can use a more convenient form of induction known as structural induction. A proof by structural induction consists of two parts. These parts are BASIS STEP: Show that the result holds for all elements specified in the basis step of the recursive definition to be in the set. RECURSIVE STEP: Show that if the statement is true for each of the elements used to construct new elements in the recursive step of the definition, the result holds for these new elements. The validity of structural induction follows from the principle of mathematical induction for the non-negative integers. To see this, let P(n) state that the claim is true for all elements of the set that are generated by n or fewer applications of the rules in the recursive step of a recursive definition. We will have established that the principle of mathematical induction implies the principle of structural induction if we can show that P(n) is true whenever n is a positive integer. In the basis step of a proof by structural induction we show that P(0) is true. That is, we show that the result is true of all elements specified to be in the set in the basis step of the definition. A consequence of the recursive step is that if we assume P(k) is true, it follows that P(k + 1) is true. When we have completed a proof using structural induction, we have shown that P(0) is true and that P(k) implies P(k + 1). By mathematical induction it follows that P(n) is true for all non-negative integers n. This also shows that the result is true for all elements generated by the recursive definition, and shows that structural induction is a valid proof technique. EXAMPLES OF PROOFS USING STRUCTURAL INDUCTION Structural induction can be used to prove that all members of a set constructed recursively have a particular property. We will illustrate this idea by using structural induction to prove results about well-formed formulae, strings, and binary trees. For each proof, we have to carry out the appropriate basis step and the appropriate recursive step. For example, to use structural induction to prove a result about the

In farsi

استقرای تعمیم یافته

==اصل استقرا تعمیم یافــته==

گاهی ممکن است با احکامی روبه رو شویم که برای n=1 برقرار نمی باشند و باید در بررسی شرط اول(مرحله مبنا)از عددی طبیعی بزرگتر استفاده کنیم به این ترتیب از اصل [[استقرا]] تعمیم یافــته استفاده می کنیم.

===مراحل استقرا تعمیم یافته===

اگر (P(nحکمی درباره [[اعداد طبیعی]]n(یا [[اعداد صحیح]]) باشد در صورتی که:

1-برای هر عدد طبیعی P(m) ، m>1 درست باشد.

2-به ازای هر عدد طبیعی ، از درستی (P(k درستی (P(k+1نتیجه شود.

آنگاه میتوان گفت حکم (P(n برای هر عدد طبیعی n=>m برقرار است.

به این ترتیب در اثبات مسائل به کمک اصل استقرای تعمیم یافته باید m مناسب را برای بررسی شرط اول بیابیم.

===مثال===

نشان دهید عدد طبیعی مناسبی مانند m وجود دارد که برای هر عدد طبیعی n بزرگتر یا مساوی m داریـم:

پاسخ:با قرار دادن مقادیر طبیعی برای m متوجه می شویم که m مناسب 3 است چرا که برای اولین بار حکم برای m=33 درست است. حال نشان میدهیم حکم برای هر عدد طبیعی درست است

1-اول به ازای n=3 درست است:

2-اکنون در این مرحله فرض ([[فرض استقرا]]) می کنیم نامساوی فوق برای هر عدد طبیعی درست باشد یعنی:

نشان میدهیم حکم داده شده برای (n=k+1 ،(k>2 درست است، یعنی:

برای این منظور از فرض استقرا استفاده کرده و به طرفین فرض عدد 2 را اضافه می کنیم، داریم:

حال با مقایسه [[نامساوی]] اخیر و حکم استقرا کافی است نشان دهیم:

برای این کار از [[اثبات بازگشتی]] کمک میگیریم:

مشاهده می شود نامساوی برای k>2 همواره درست است و چون تمامی روابط برگشت پذیرند، لذا برقرار بوده و به این ترتیب حکم برای هر عدد طبیعی برقرار است.

== منابع ==

https://en.wikipedia.org/wiki/Induction

== پیوند به بیرون ==

Discrete Mathematics and its Applications- Kenneth H. Rosen