I am trying to prove the following bound using induction (where N>D):
∑Di=0(Ni)≤ND+1
I would appreciate any help on how to prove this. Thanks.
Currently I have looked at low values of D (base cases) but I don't understand how to formulate an induction step without using any prior information on the final result.
D=0: ∑0i=0(Ni)≤N0+1⇔1≤2
D=1: ∑1i=0(Ni)≤N1+1⇔N+1≤N+1
D=2: ∑2i=0(Ni)≤N2+1⇔N22+N2+1≤N22+N22+1≤N2+1
Maybe a first step in solving this is:
∑Di=0(Ni)=∑D−1i=0(Ni)+(ND) ??
No comments:
Post a Comment