做 whk 时发现的一个组合恒等式

$3\sum2^i{m-i \choose i}=2^{m+1}+(-1)^m$

求证法。

验证程序，如果有需要的话：

#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned long long
#define db double
#define fo(i,a,b) for(int i=(a);i<=(b);i++)
#define ro(i,a,b) for(int i=(a);i>=(b);i--)
#define pri printf
using namespace std;
inline int rd()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*f;
}

const int maxn=2005;
const ll mod=1e9+9;
int n,k;
int a[maxn],b[maxn],r[maxn];
ll dp[maxn][maxn];
ll g[maxn];
ll jc[maxn+5];
void init()
{
	jc[0]=1;
	fo(i,1,maxn) jc[i]=jc[i-1]*i%mod;
}
ll ksm(ll u,ll v)
{
	ll ret=1;
	while(v)
	{
		if(v&1) ret=ret*u%mod;
		u=u*u%mod;
		v>>=1;
	}
	return ret;
}
ll ni(ll u){return ksm(u,mod-2);}
ll c(ll u,ll v){if(u<v) return 0; return jc[u]*ni(jc[v])%mod*ni(jc[u-v])%mod;}
int main()
{
	init();
	
	fo(m,1,20)
	{
		ll ans1=0;
		fo(i,0,m) ans1=(ans1+ksm(2,i)*c(m-i,i)%mod)%mod;
		ans1=(ans1*3)%mod;
		ll ans2=(ksm(2,m+1)+ksm(mod-1,m))%mod;
		pri("%lld %lld\n",ans1,ans2);
	}
	
	
	
	
	return 0;
}