python - 我如何证明一个特定的序列算法总是奇怪的？

Question

给定序列 a ₁ =1, a ₂ =3, a _k =a _k-2 +2a _k-1 对于所有整数 k >= 3

我如何证明：对于所有整数 n >= 1，给定序列 a ₁， a ₂ ...a _k如上所述，a _n总是奇数。

我尝试使用下面的 python 代码定义奇数/偶数序列，但我无法解决问题：

def odd_even(n, k):
    x = list()
    i = 1
    while i < n: 
        x.append(i)
        i = i + 2
    i = 2
    while i < 2:
        x.append(i)
        i = i + 2
    
    return (a[k - 1])

# Driver code
n = 10
k = 3

odd_even(n, k)

标签： pythonalgorithm

Answer 1

你不能用这样的代码证明一个定理，尽管你可以希望自己确信它适用于一些有限的输入样本。

这样的事情可以通过归纳来证明。1 为奇数，3 为奇数。a_k-2 + 2 a_k-1当是奇数时，表达式是奇数，a_k-2因为2 a_k-1无论 的奇偶性如何，它总是偶数a_k-1。既然a_1是奇数，每一个都a_2n+1必须是奇数。既然a_2是奇数，每一个都a_2n+2必须是奇数。QED。