2
$\begingroup$

$$ ((n+1)H_n - (n+1)) + H_{n+1} = (n+2)H_{n+1} - (n+2) $$ I need to prove the above statement.

  • 0
    doesn't merely using the definition of $H_n$ work?2010-11-03
  • 1
    $H_{n+1}=H_n+1/(n+1)$2010-11-03
  • 0
    I should have added that I had gotten that far, but I can't figure what to do with that.2010-11-03
  • 1
    @Mark: cancel as many terms as you can.2010-11-03
  • 0
    Do you really need to prove it by induction? In my answer I assumed not.2010-11-03
  • 0
    It's part of an inductive proof ($H_1+H_2+...+H_n = (n+1)H_n - (n+1)$)2010-11-03
  • 0
    Thanks for all the help, I've now fully proven the statement.2010-11-03

2 Answers 2

5

Hint: Your identity is equivalent to

$$(n+1)(H_{n+1}-H_{n})=1,$$

which is something you can deduce by a simple algebraic manipulation.

  • 1
    Thank you so much. I feel like an idiot now (like always). Anyway, thanks for the help.2010-11-03
0

HINT $\ $ If $\rm\:f(n)\:$ satsifies a first-order recurrence $\rm\ \ f(n+1) = a\ f(n) + b\ $ then it may be used as a rewrite rule to reduce $\rm\ c_0\ f(n) + c_1\ f(n+1) + \:\cdots\: + c_k\ f(n+k)\ $ to the form $\rm\ d\ f(n) + e\:.\ $ Said in operator form, if $\rm \ S^2 = a\ S + b\ $ then $\rm\ f(S)\ \:mod\:\ (S^2-a\ S-b)\ =\ c\ S + d\ $ has degree 1, since one can eliminate $\rm\:S^n,\ n>2\ $ via the rewrite rule $\rm\: S^2 \to a\ S + b\:$. In essence one is employing the division / Euclidean algorithm to compute a remainder in a polynomial ring of operators. Precisely the same method works for solutions of any (monic) linear recurrence or differential equation.