Recursive Definitions and Proofs in Mathematics

This article discusses recursive definitions and proofs in mathematics, covering topics such as base case, recursive step, and induction. It includes solved examples and explanations, and also provides study material, essays, and dissertations on this topic available at Desklib.

Question 1
a) A ( m ,n )=¿
For A(1 , n), m=1 hence for all positive integers i.e. n ≥ 1, we have
A ( 1 , n )= { 2 for n=1
A ( 0 , A (1 , n−1 ) ) for n ≥ 2
But A ( m ,n )=2 n if m=0 hence A ( 0 , A ( 1 ,n−1 ) )=2 n for n ≥2.
Therefore, A ( 1 , n ) = { 2 for n=1
2 n for n ≥ 2
By induction, we show that if A(1 , k ) holds, then A(1 , k +1) also holds where
A ( 1 , k )=2k for k ≥1
We show that the statement holds for k =1.
A ( 1,1 )=21=2 which is equal to the previous calculation.
Assume that A ( 1 , k ) holds, then we show that A(1 , k +1) holds
i.e show that 2 ( k +1 ) =2(k+1 )
For k ≥ 2 A ( 1 , k +1 ) = A(0 , A (1 , k+ 1−1))
¿ A ( 0 , A ( 1 ,k ) )= A ( 0 , 2k )
¿ 2(2k )
Hence A ( 1 , k +1 )=2k +1 proving that A ( 1 , n )=2n for all positive integers
b) a↑↑1=aa
a ↑ ↑ ( k +1 ) =aa( k+ 1)
¿ aa(ak)
¿ aa( a¿¿k) ¿
We can define a(ak) as a ↑ ↑ k hence we have
a ↑ ↑ ( k +1 )=aa ↑↑ k
c) A ( 2 , n )= { 2 for n=1
A ( 1 , A ( 2 , n−1 ) ) for n ≥2
Solving by induction, we prove that for all positive integers, i.e. n ≥ 1, A ( 2 , n ) =2 ↑↑ n
Show that if A ( 2 , k ) holds, then A( 2, k +1) also holds
For k =1, A ( 2,1 )=2 which holds since 2 ↑↑ 1=2
For k =2, A ( 2,2 )= A ( 1 , A ( 2,1 ) )= A ( 1,2 )=2 n=4
For k ≥ 2 , A ( 1 , k +1 )= A ( 1 , A ( 2 ,k ) ) where A ( 2 , k ) =2 ↑↑ k
Since values of 2 ↑↑ k are greater than 2, A ( 1 , A ( 2 , k ) ) =2∗2 ↑ ↑k hence at
k +1 , A ( 1 ,k + 1 ) =2 ↑↑(k +1) proving that (2, 𝑛) = 2 ↑↑ 𝑛 for all positive integers 𝑛.

d) A ( 3 , n )= { 2 for n=1
A ( 2 , A (3 , n−1 ) ) for n ≥ 2
From (c) above, A ( 2 , n )=2 ↑↑ n hence, A ( 3 , n ) =2 ↑ ↑ A( 3 ,n−1)
Where A ( 3 , n−1 ) =A ( 2 , A ( 3 , n−2 ) )
¿ 2 ↑↑ ↑ A ( 3 , n−2 )
¿ 2 ↑↑(2 ↑↑ A ( 3 , n−3 ))
Continued expansion of the series leads to generation of an equation of the form
A ( 3 , n )=2 ↑ ↑↑ n
Proof by induction
We show that if A ( 3 , n ) holds, then A ( 3 , n+1 ) also holds for all positive integers.
We assume it is true for the base integer, 1.
For n=1, A ( 3 , n )=2 which is true since 2 ↑↑ ↑1=2
For n+1, A ( 3 , n+1 ) = A (2,2↑ ↑↑ n) but A ( 2 , n )=2 ↑↑ n hence we have
A ( 3 , n+1 )=2 ↑↑ ( 2 ↑↑ ↑ n )=2 ↑↑ ↑(k +1), proving that it is true for n+1
Question 2
Recursive definition of base case and recursive step.
For this case, the base case is 2 ∈ S and the recursive step is
if n ∈ S , then2 n ∈ S
if n ∈ S , then n2 ∈ S
Let x be a member of S i. e x=2p , p ∈ N
Let y be an arbitrary member of S
Then, either y=2 x or y=x2
If y=2 x, then y=2 x=2∗2p=2p +1∈S
So y=2p+1 , p ∈ N ∈ S
If ¿ x2 , then y=x2=( x p)2= x2 p ∈ S
So y=x2 p , p ∈ N
Hence y also has theform y=2k for k ∈ N . Since y is arbitrary, we conclude that S has the
property P, proving the statement.

Question 3
B={010,00010,0101,0000010,000101,000101 , … }
Clearly, 010 is of length 3 and has an even number of zeros.
For any x ∈ B, assume that it has even number of zeros. Then x produces two strings 00 x , x 1in
B where they all have even number of zeros hence every element contains even number of zeros.
Question 4
Each element of S is given by a finite level of recursion from 6 in two steps
When the level of recursion k =0,we get only 6 ∈ S which clearly ends with 6
When k =1, we get 2 elements: 62 =36 and 3∗6−2=16. Clearly both elements end with 6.
We show that all elemnts of S obtained by k levels of recursion end with 6. Suppose n is any
element of S obtained by (k + 1) level of recursion. Then, n=3 m−2 or n=m2 for some number m
ending with 6;
We use the algebraic definition m=10 z +6 for some non-negative integer z.
When n=3 m−2=3 ( 10 z+ 6 )−2
¿ ( 3 z+1 )∗10+6 which ends with 6
When n=m2=(10 z +6)2=100 z2+120 z +36 which ends with 6. Thus all elements of S obtained
by any level of recursion are numbers ending with 6.
References
Bluman, A. G. (2001). elementary statistics with CDROM. McGraw-Hill Companies.
Triola, M. F. (2014). elementary statistics. Pearson.