Combinatorial proof for $n \in \mathbb{N}$:
$$\sum_{k=0}^n \sum_{j=0}^n {{k}\choose{j}} {{n-k}\choose{j}} = \sum_{m=0}^n {{n+1}\choose{2m+1}} $$
I know that the LHS can be written as: $\sum_{k=0}^n \sum_{j=0}^n {{k}\choose{j}} {{n-k}\choose{j}} = \sum_{k=0}^n \sum_{j=0}^n {{k}\choose{k-j}} {{n-k}\choose{j}}$
That way I see that on the RHS, as we enumerate new elements of the external sum, we divide group of $n$ elements in 2 groups - using $k$, we put separation between subgroup of $k$ elements and a subgroup of $n - k$ elements. Next, we choose $k-j$ from the first one and $j$ from the other one. With alternating $j$, we get different possibilities, but in each component of the whole sum that way we choose $k-j + j = k$ elements.
The thing that I don't get is the RHS - why would our way of counting possible elements that sum to $k$ be equal to choosing $2m+1$ elements out of a group of $n+1$ elements?
The Left Hand Side is equal to $\sum_{k=0}^n \sum_{j = 0}^n {k \choose k-j } {n-k \choose j} = 2^n$, since we choose all possible subsets of $[n] = \{1,...,n\}$.
As mentioned in one of the comments by Thomas Andrews, we have ${n+1 \choose 2m+1} = {n \choose 2m} + {n \choose 2m+1} \implies \sum_{m \geq 0} {n+1 \choose 2m+1} = \sum_{m \geq 0} {n \choose m} = 2^n$.
Combinatorial proof of relation:${n+1 \choose 2m+1} = {n \choose 2m} + {n \choose 2m+1}$:
The number of ways of choosing $2m+1$ elements out of $n+1$ elements : ${n+1 \choose 2m+1}$ is equal to number of ways of choosing $2m+1$ elements without including a fixed element ${n \choose 2m+1}$ + number of ways of choosing $2m$ elements adding that one fixed element ${n \choose 2m}$.