ReAl (01.03.2009 16:28, просмотров: 144) ответил POV на Дык, это ясно :) А где взять эти две суммы не сложением кучи данных, а одной-двумя формулами. Впрочем, как выше написал, решение уже нашел.. хотя и без четкой формализации, чего не люблю.
Пока степени малые, оно как-то геометрически можно себе подсобить. N2/2 - это площадь прямоугольнгого треугольника со стороной N. Но нам она нужна в "хотя бы задетых" квадратиках 1*1, N квадратиков попадает на диагональ и надо добавить N/2 потерянной площади.
С суммой квадратов я начал плясать от пирамиды - N3/3 - это объём пирамиды с основанием N^2 и высотой N.
N2/2 + N/2 - число кубиков, задетых косыми гранями, отрезающими (кроме косого ребра) по 1/2 объёма, но граней две, так что потери будут как бы N2/2 + N/2
Но на ребре мы добавляем лишнее, на этом я остановился, пришлось заняться другим.
Ну так вот на ребре каждому кубику на предыдущем этапе дважды добавляется по 1/3 объёма, кубиков на ребре N.
Итого (N3/3) + (N2/2 + N/2) - N/3 = искомое.
Для кубов не просите, 4-мерного пространственного воображения у меня нет :-)
Но исходя из формул для 2D и 3D можно попытаться уловить формулу для 4D и доказать её матиндукцией.