引理: ∑ ϵ k ∈ { − 1 , 1 } , 1 ≤ k ≤ n ( ∑ k = 1 n ϵ k a k ) 2 = 2 n ∑ k = 1 n a k 2 \sum_{\epsilon_k\in \{-1,1\},1\le k\le n}(\sum^n_{k=1}\epsilon_ka_k)^2=2^n\sum^n_{k=1}a_k^2 ϵk∈{−1,1},1≤k≤n∑(k=1∑nϵkak)2=2nk=1∑nak2
证明: n = 1 时, L H S = 2 a 1 2 , R H S = 2 a 1 2 ,成立 n=1时,LHS=2a_1^2,RHS=2a_1^2,成立 n=1时,LHS=2a12,RHS=2a12,成立
设 n 时成立,证明 n + 1 时情况: 设n时成立,证明n+1时情况: 设n时成立,证明n+1时情况:
∑ ϵ k ∈ { − 1 , 1 } , 1 ≤ k ≤ n + 1 ( ∑ k = 1 n + 1 ϵ k a k ) 2 \sum_{\epsilon_k\in \{-1,1\},1\le k\le n+1}(\sum^{n+1}_{k=1}\epsilon_ka_k)^2 ϵk∈{−1,1},1≤k≤n+1∑(k=1∑n+1ϵkak)2
= ∑ ϵ k ∈ { − 1 , 1 } , 1 ≤ k ≤ n + 1 ( ( ∑ k = 1 n ϵ k a k ) 2 + 2 ( ∑ k = 1 n ϵ k a k ) ∗ ϵ n + 1 a n + 1 + a n + 1 2 ) =\sum_{\epsilon_k\in \{-1,1\},1\le k\le n+1}((\sum^n_{k=1}\epsilon_ka_k)^2+2(\sum^n_{k=1}\epsilon_ka_k)*\epsilon_{n+1}a_{n+1}+a_{n+1}^2) =ϵk∈{−1,1},1≤k≤n+1∑((k=1∑nϵkak)2+2(k=1∑nϵkak)∗ϵn+1an+1+an+12)
= 2 ∑ ϵ k ∈ { − 1 , 1 } , 1 ≤ k ≤ n + 2 ∑ ϵ n + 1 ∈ { − 1 , 1 } ϵ n + 1 a n + 1 ∑ ϵ k ∈ { − 1 , 1 } , 1 ≤ k ≤ n ϵ k a k + 2 n + 1 × a n + 1 2 =2\sum_{\epsilon_k\in \{-1,1\},1\le k\le n}+2\sum_{\epsilon_{n+1}\in\{-1,1\}}\epsilon_{n+1}a_{n+1}\sum_{\epsilon_k\in \{-1,1\},1\le k\le n}\epsilon_ka_k+2^{n+1}\times a_{n+1}^2 =2ϵk∈{−1,1},1≤k≤n∑+2ϵn+1∈{−1,1}∑ϵn+1an+1ϵk∈{−1,1},1≤k≤n∑ϵkak+2n+1×an+12
= 2 n + 1 ∑ k = 1 n a k 2 + 2 n + 1 × a n + 1 2 = R H S 证毕 =2^{n+1}\sum^n_{k=1}a_k^2+2^{n+1}\times a_{n+1}^2=RHS \ \ \ \ \ \ 证毕 =2n+1k=1∑nak2+2n+1×an+12=RHS 证毕
二分搜索边界问题的简单结论
2024-07-20 15:50:02 62 阅读