Proving that $\sum_{j=0}^n {n \choose j} = {n \choose 0} + ... + {n \choose n} = 2^n$

Question

I'm looking for a proof verification, precisely at the end of the proof. We proceed by induction on $n$.

Pf. Base case $n = 1$,$$\sum_{j=0}^1 {1 \choose j} = {1 \choose 0} + {1 \choose 1} = 1 + 1 = 2^1$$ Notice also for $n=2$, $$\sum_{j=0}^2 {2 \choose j} = {2 \choose 0} + {2 \choose 1} + {2 \choose 2} = 1 + 2 + 1 = 2^2$$ Now, suppose that for $k\in\mathbb{N}$ it is true that $$\sum^k_{j=0} {k \choose j} = 2^k$$ Then, by Pascal's identity, $$\sum^k_{j=0} {k \choose j} + \sum^k_{j=0} {k \choose j-1} = \sum^{k+1}_{j=0} {k+1 \choose j} = 2^{k+1}$$ Since $k$ is any natural number, it should then also work for $k+1$.

My reservations are that I'm using the assumption incorrectly or misusing the assumption by not starting with the assumption. Any clarity is appreciated.

Edit: It seems that changing the bound on the second sum in this equation

Then, by Pascal's identity, $$\sum^k_{j=0} {k \choose j} + \sum^k_{j=0} {k \choose j-1} = \sum^{k+1}_{j=0} {k+1 \choose j} = 2^{k+1}$$

to $k+1$ yielded the quickest fix to the original proof, with the convention that, as Brian M. Scott pointed out: ${n \choose k}$ is 0 if $k$ is a negative integer.

Answer 1

To salvage your proof, use Pascal's identity in $$ \sum^{k+1}_{j=0} {k \choose j} + \sum^{k+1}_{j=0} {k \choose j-1} = \sum^{k+1}_{j=0} {k+1 \choose j}. $$ Both summands on the LHS are then equal to $2^k$, by your induction hypothesis, with the aid of the convention ${k\choose j}=0$ when $j<0$ or $j>k$.

Answer 2

Your argument is incorrect.

First you state:

$$\sum^k_{j=0} {k \choose j} = 2^k$$

and then claim:

$$\sum^k_{j=0} {k \choose j} + \sum^k_{j=0} {k \choose j-1} = \sum^{k+1}_{j=0} {k+1 \choose j} = 2^{k+1}$$

However:

$$\sum^k_{j=0} {k \choose j-1}=\sum^k_{j=0} {k \choose j}-{k\choose k}=2^k-1$$

so your LHS = $2^{k+1}-1$.