Introduction To Mathematical Induction

 

# Verification of Mathematical Induction Concepts using Python

def verify_sum_formula(n):
    """
    Example 1: Verifies if the sum of 1 to n matches n*(n+1)/2
    """
    actual_sum = sum(range(1, n + 1))
    formula_sum = (n * (n + 1)) // 2
    return actual_sum == formula_sum


def verify_divisibility(n):
    """
    Example 2: Verifies if (n^3 - n) is completely divisible by 3
    """
    expression_value = (n**3) - n
    return expression_value % 3 == 0


# --- PROGRAM EXECUTION / SIMULATION ---
max_test_value = 100

# 1. Simulate Base Case (n = 1)
print("--- STEP 1: BASE CASE VERIFICATION ---")
print(f"Base Case (n=1) for Sum Formula: {verify_sum_formula(1)}")
print(f"Base Case (n=1) for Divisibility: {verify_divisibility(1)}")
print()

# 2. Simulate Inductive Step across a large range
print("--- STEP 2: INDUCTIVE CHAIN VERIFICATION ---")
all_sums_valid = True
all_divs_valid = True

for k in range(1, max_test_value):
    # If it holds for k, check if it holds for k + 1
    if verify_sum_formula(k):
        if not verify_sum_formula(k + 1):
            all_sums_valid = False
            
    if verify_divisibility(k):
        if not verify_divisibility(k + 1):
            all_divs_valid = False

print(f"Inductive chain holds for Sum Formula up to n={max_test_value}: {all_sums_valid}")
print(f"Inductive chain holds for Divisibility up to n={max_test_value}: {all_divs_valid}")