первая формула не работает уже при k=1.
Есть похожая формула:
\sum_{n=0}^k {2k+1 \choose 2n } 2^{2n} B_{2n} = 2k+1

Числа Бернулли обычно определяются как:
B_0=1, B_1=-1/2, B_2=1/6, B_3=0, B_4=-1/30, B_5=0, ...
см. http://mathworld.wolfram.com/BernoulliNumber.html

Если Вашу формулу исправить под стандартное определение, то тогда она принимает вид:
\sum_{n=1}^k {2k+1 \choose 2n} 2^{2n} B_{2n} = 2k
Если сюда к каждой части прибавить по единице, то получится та самая формула:
\sum_{n=0}^k {2k+1 \choose 2n } 2^{2n} B_{2n} = 2k+1

В "Конкретной математике" и у Риордана тоже определяется как на MathWorld. Хотя это тоже американцы, да.

Кстати, там же на MathWorld есть определение и "ваших" чисел (в конце), только к ним еще звезды пририсованы.

да и с остальными формулами что-то численно не срастается.
Не могли бы продемонстрировать формулы для k=1,2,3 ?

В "американских" обозначениях формула приобретает вид:
E_{2k} = - \sum_{n=1}^k {2k \choose 2n} E_{2k-2n}
или
\sum_{n=0}^k {2k \choose 2n} E_{2k-2n} = 0
что есть частный случай формулы (21) на http://mathworld.wolfram.com/EulerNumber.html

Опять же в "американских" обозначениях формула приобретает вид:
B_{2k} = { 2k \over {2^{2k}(2^{2k}-1)} } \sum_{n=1}^k {2k-1 \choose 2n-1 } E_{2k-2n} =
= { 2k \over {2^{2k}(2^{2k}-1)} } \sum_{n=0}^{k-1} {2k-1 \choose 2n } E_{2n}.

Откуда видно, что она является следствием формулы (21) на http://mathworld.wolfram.com/EulerNumber.html и формул (1)-(2) на http://mathworld.wolfram.com/TangentNumber.html